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\boxtimes 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. We give three applications of this result: (1) improved upper bounds for the weak coloring numbers of graphs excluding a given minor, (2) an improved product structure theorem for apex-minor-free graphs, and (3) improved upper bounds for the p -centered chromatic number of graphs excluding a given minor.
Authors
- Vida Dujmović (ORCID: https://orcid.org/0000-0001-7250-0600)
- Gwenaël Joret (ORCID: https://orcid.org/0000-0002-7157-6694)
- Pat Morin (ORCID: https://orcid.org/0000-0003-0471-4118)
- David R. Wood (ORCID: https://orcid.org/0000-0001-8866-3041)
- Jędrzej Hodor (ORCID: https://orcid.org/0000-0002-2564-7121)
- Robert Hickingbotham (ORCID: https://orcid.org/0009-0007-1817-8295)
- Clément Rambaud (ORCID: https://orcid.org/0009-0003-0706-3477)
- Hoang La (ORCID: https://orcid.org/0000-0002-3602-0519)
- Piotr Micek (ORCID: https://orcid.org/0000-0001-9796-5375)
Institutions
- Jagiellonian University (PL)
- Centre National de la Recherche Scientifique (FR)
- Université Libre de Bruxelles (BE)
- Institut national de recherche en sciences et technologies du numérique (FR)
- University of Ottawa (CA)
- Université Côte d'Azur (FR)
- École Normale Supérieure - PSL (FR)
- École Normale Supérieure (BI)
- Institut de Biologie de l'École Normale Supérieure (FR)
- Monash University (AU)
- Carleton University (CA)
Publication Details
- Journal
- COMBINATORICA
- Published
- 2025-11-07
- DOI
- https://doi.org/10.1007/s00493-025-00168-w
- Primary Topic
- Advanced Graph Theory Research
- Type
- article
- Field-Weighted Citation Impact
- 0.00