Product structure of graphs with an excluded minor

Abstract

This paper shows that $K_t$-minor-free (and $K_{s,t}$-minor-free) graphs $G$ are subgraphs of products of a tree-like graph $H$ (of bounded treewidth) and a complete graph $K_m$. Our results include optimal bounds on the treewidth of $H$ and optimal bounds (to within a constant factor) on $m$ in terms of the number of vertices of $G$ and the treewidth of $G$. These results follow from a more general theorem whose corollaries include a strengthening of the celebrated separator theorem of Alon, Seymour, and Thomas [J. Amer. Math. Soc. 1990] and the Planar Graph Product Structure Theorem of Dujmović et al. [J. ACM 2020].

arXiv commentMain results are not in v1. Theorem 4 is new in v3. v5 is a major update, now with a proof of the Planar Graph Product Structure Theorem. v6 includes applications to p-centred colouring and appendix on simple treewidth

References in corpus (11)

• Planar graphs have bounded queue-number
• Layered Separators in Minor-Closed Graph Classes with Applications
• Adjacency Labelling for Planar Graphs (and Beyond)
• Improved bounds for centered colorings
• Planar graphs have bounded nonrepetitive chromatic number
• Sparse universal graphs for planarity
• Notes on Graph Product Structure Theory
• Improved product structure for graphs on surfaces
• Separating layered treewidth and row treewidth
• Product structure of graph classes with bounded treewidth
• Product structure extension of the Alon--Seymour--Thomas theorem

Cited by in corpus (2)

• The grid-minor theorem revisited
• Edge separators for graphs excluding a minor