The grid-minor theorem revisited

Abstract

We prove that for every planar graph $X$ of treedepth $h$, there exists a positive integer $c$ such that for every $X$-minor-free graph $G$, there exists a graph $H$ of treewidth at most $f(h)$ such that $G$ is isomorphic to a subgraph of $H⊠K_c$. This is a qualitative strengthening of the Grid-Minor Theorem of Robertson and Seymour (JCTB 1986), and treedepth is the optimal parameter in such a result. As an example application, we use this result to improve the upper bound for weak coloring numbers of graphs excluding a fixed graph as a minor.

References in corpus (18)

• Planar graphs have bounded queue-number
• Improper Colourings inspired by Hadwiger's Conjecture
• Defective colouring of graphs excluding a subgraph or minor
• Adjacency Labelling for Planar Graphs (and Beyond)
• Improved bounds for centered colorings
• Planar graphs have bounded nonrepetitive chromatic number
• Clustered 3-Colouring Graphs of Bounded Degree
• Coloring planar graphs with three colors and no large monochromatic components
• Sparse universal graphs for planarity
• Partitioning $H$-minor free graphs into three subgraphs with no large components
• Clustered Colouring in Minor-Closed Classes
• Clustered Variants of Hajós' Conjecture
• Approximating pathwidth for graphs of small treewidth
• Product structure of graphs with an excluded minor
• Excluding a ladder
• Bad News for Chordal Partitions
• The Excluded Tree Minor Theorem Revisited
• Defective coloring is perfect for minors