{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,29]],"date-time":"2025-12-29T13:23:46Z","timestamp":1767014626237,"version":"3.48.0"},"reference-count":44,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2025,11,7]],"date-time":"2025-11-07T00:00:00Z","timestamp":1762473600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,11,7]],"date-time":"2025-11-07T00:00:00Z","timestamp":1762473600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001779","name":"Monash University","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100001779","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2025,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    We prove that for every planar graph\n                    <jats:italic>X<\/jats:italic>\n                    of treedepth\n                    <jats:italic>h<\/jats:italic>\n                    , there exists a positive integer\n                    <jats:italic>c<\/jats:italic>\n                    such that for every\n                    <jats:italic>X<\/jats:italic>\n                    -minor-free graph\n                    <jats:italic>G<\/jats:italic>\n                    , there exists a graph\n                    <jats:italic>H<\/jats:italic>\n                    of treewidth at most\n                    <jats:italic>f<\/jats:italic>\n                    (\n                    <jats:italic>h<\/jats:italic>\n                    ) such that\n                    <jats:italic>G<\/jats:italic>\n                    is isomorphic to a subgraph of\n                    <jats:inline-formula>\n                      <jats:tex-math>$$H\\boxtimes K_c$$<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    . This is a qualitative strengthening of the Grid-Minor Theorem of Robertson and Seymour\u00a0(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\n                    <jats:italic>p<\/jats:italic>\n                    -centered chromatic number of graphs excluding a given minor.\n                  <\/jats:p>","DOI":"10.1007\/s00493-025-00168-w","type":"journal-article","created":{"date-parts":[[2025,11,7]],"date-time":"2025-11-07T11:46:22Z","timestamp":1762515982000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["The Grid-Minor Theorem Revisited"],"prefix":"10.1007","volume":"45","author":[{"given":"Vida","family":"Dujmovi\u0107","sequence":"first","affiliation":[]},{"given":"Robert","family":"Hickingbotham","sequence":"additional","affiliation":[]},{"given":"J\u0119drzej","family":"Hodor","sequence":"additional","affiliation":[]},{"given":"Gwena\u00ebl","family":"Joret","sequence":"additional","affiliation":[]},{"given":"Hoang","family":"La","sequence":"additional","affiliation":[]},{"given":"Piotr","family":"Micek","sequence":"additional","affiliation":[]},{"given":"Pat","family":"Morin","sequence":"additional","affiliation":[]},{"given":"Cl\u00e9ment","family":"Rambaud","sequence":"additional","affiliation":[]},{"given":"David R.","family":"Wood","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,11,7]]},"reference":[{"issue":"1","key":"168_CR1","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/0095-8956(86)90026-2","volume":"41","author":"Thomas Andreae","year":"1986","unstructured":"Andreae, Thomas: On a pursuit game played on graphs for which a minor is excluded. J. Combin. Theory, Series B 41(1), 37\u201347 (1986)","journal-title":"J. Combin. Theory, Series B"},{"key":"168_CR2","unstructured":"Bose, P., Dujmovi\u0107, V., Javarsineh, M., Morin, P.: Asymptotically optimal vertex ranking of planar graphs, 2023. arXiv:2007.06455"},{"issue":"3","key":"168_CR3","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1017\/S0963548323000457","volume":"33","author":"R Campbell","year":"2024","unstructured":"Campbell, R., Clinch, K., Distel, M., Gollin, J.P., Hendrey, K., Hickingbotham, R., Huynh, T., Illingworth, F., Tamitegama, Y., Tan, J., Wood, D.R.: Product structure of graph classes with bounded treewidth. Combin. Probab. Comput. 33(3), 351\u2013376 (2024). arXiv:2206.02395","journal-title":"Combin. Probab. Comput."},{"key":"168_CR4","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Chuzhoy, J.: Polynomial bounds for the grid-minor theorem. J. ACM, 63(5), 2016. arXiv:1305.6577","DOI":"10.1145\/2820609"},{"key":"168_CR5","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/j.jctb.2020.09.010","volume":"146","author":"T Chuzhoy","year":"2021","unstructured":"Chuzhoy, T., Tan, Z.: Towards tight(er) bounds for the excluded grid theorem. J. Combin. Theory, Series B 146, 219\u2013265 (2021). arXiv:1901.07944","journal-title":"J. Combin. Theory, Series B"},{"issue":"4","key":"168_CR6","doi-asserted-by":"publisher","first-page":"481","DOI":"10.1002\/jgt.3190200412","volume":"20","author":"Guoli Ding","year":"1995","unstructured":"Ding, Guoli, Oporowski, Bogdan: Some results on tree decomposition of graphs. J. Graph Theory 20(4), 481\u2013499 (1995)","journal-title":"J. Graph Theory"},{"issue":"2","key":"168_CR7","first-page":"6","volume":"24","author":"M Distel","year":"2022","unstructured":"Distel, M., Hickingbotham, R., Huynh, T., Wood, D.R.: Improved product structure for graphs on surfaces. Discrete Math. Theor. Comput. Sci. 24(2), 6 (2022). arXiv:2112.10025","journal-title":"Discrete Math. Theor. Comput. Sci."},{"issue":"6","key":"168_CR8","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1145\/3477542","volume":"68","author":"V Dujmovi\u0107","year":"2021","unstructured":"Dujmovi\u0107, V., Esperet, L., Gavoille, C., Joret, G., Micek, P., Morin, P.: Adjacency labelling for planar graphs (and beyond). J. ACM 68(6), 42 (2021). arXiv:2003.04280","journal-title":"J. ACM"},{"issue":"1","key":"168_CR9","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1017\/S0963548321000213","volume":"31","author":"V Dujmovi\u0107","year":"2022","unstructured":"Dujmovi\u0107, V., Esperet, L., Morin, P., Walczak, B., Wood, D.R.: Clustered 3-colouring graphs of bounded degree. Combin. Probab. Comput. 31(1), 123\u2013135 (2022). arXiv:2002.11721","journal-title":"Combin. Probab. Comput."},{"key":"168_CR10","doi-asserted-by":"crossref","unstructured":"Dujmovi\u0107, V., Esperet, L., Morin, P., Wood, D.R.: Proof of the clustered Hadwiger conjecture. In Proc. 64th IEEE Annual Symposium on Foundations of Computer Science (FOCS \u201923, pages 1921\u20131930, 2023. arXiv:2306.06224","DOI":"10.1109\/FOCS57990.2023.00116"},{"key":"168_CR11","doi-asserted-by":"crossref","unstructured":"Dujmovi\u0107, V., Hickingbotham, R., Hodor, J., Joret, G., La, H., Micek, P., Morin, P., Rambaud, C., Wood, D.R.: The grid-minor theorem revisited, 2023. arXiv:2307.02816","DOI":"10.1137\/1.9781611977912.48"},{"key":"168_CR12","doi-asserted-by":"crossref","unstructured":"Dujmovi\u0107, V., Joret, G., Micek, P., Morin, P., Ueckerdt, T., Wood, D.R.: Planar graphs have bounded queue-number. J. ACM, 67(4), 2020. arXiv:1904.04791","DOI":"10.1145\/3385731"},{"key":"168_CR13","doi-asserted-by":"crossref","unstructured":"Dujmovi\u0107, V., Esperet, L., Joret, G., Walczak, B., Wood, D.R.: Planar graphs have bounded nonrepetitive chromatic number. Advances in Combinatorics, #5, 2020. arXiv:1904.05269","DOI":"10.19086\/aic.12100"},{"issue":"1","key":"168_CR14","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1017\/S0963548323000275","volume":"33","author":"V Dujmovi\u0107","year":"2024","unstructured":"Dujmovi\u0107, V., Hickingbotham, R., Joret, G., Micek, P., Morin, P., Wood, D.R.: The excluded tree minor theorem revisited. Combin. Probab. Comput. 33(1), 85\u201390 (2024). arXiv:2303.14970","journal-title":"Combin. Probab. Comput."},{"issue":"5","key":"168_CR15","doi-asserted-by":"publisher","first-page":"833","DOI":"10.1016\/j.ejc.2012.12.004","volume":"34","author":"Zden\u011bk Dvo\u0159\u00e1k","year":"2013","unstructured":"Dvo\u0159\u00e1k, Zden\u011bk: Constant-factor approximation of the domination number in sparse graphs. European J. Combin. 34(5), 833\u2013840 (2013). arXiv:1110.5190","journal-title":"European J. Combin."},{"key":"168_CR16","doi-asserted-by":"crossref","unstructured":"D\u0229bski, M., Felsner, S., Micek, P., Schr\u00f6der, F.: Improved bounds for centered colorings. Advances in Combinatorics, #8, 2021. arXiv:1907.04586","DOI":"10.19086\/aic.27351"},{"issue":"4","key":"168_CR17","doi-asserted-by":"publisher","first-page":"551","DOI":"10.1017\/S0963548314000170","volume":"23","author":"L Esperet","year":"2014","unstructured":"Esperet, L., Joret, G.: Colouring planar graphs with three colours and no large monochromatic components. Combin., Probab. Comput. 23(4), 551\u2013570 (2014). arXiv:1303.2487","journal-title":"Combin., Probab. Comput."},{"issue":"4","key":"168_CR18","doi-asserted-by":"publisher","first-page":"1333","DOI":"10.1112\/jlms.12781","volume":"108","author":"L Esperet","year":"2023","unstructured":"Esperet, L., Joret, G., Morin, P.: Sparse universal graphs for planarity. J. London Math. Soc. 108(4), 1333\u20131357 (2023). arXiv:2010.05779","journal-title":"J. London Math. Soc."},{"key":"168_CR19","doi-asserted-by":"crossref","unstructured":"Fraigniaud, P., Nisse, N.: Connected treewidth and connected graph searching. In Jos\u00e9\u00a0R. Correa, Alejandro Hevia, and Marcos\u00a0A. Kiwi, editors, Proc. 7th Latin American Symposium on Theoretical Informatics, LATIN 2006, volume 3887 of Lecture Notes in Comput. Sci., pages 479\u2013490. Springer, 2006","DOI":"10.1007\/11682462_45"},{"key":"168_CR20","doi-asserted-by":"crossref","unstructured":"Groenland, C., Joret, G., Nadara, W., Walczak, B.: Approximating pathwidth for graphs of small treewidth. ACM Trans. Algorithms, 19(2), 2023. arXiv:2008.00779","DOI":"10.1145\/3576044"},{"issue":"4","key":"168_CR21","doi-asserted-by":"publisher","first-page":"2467","DOI":"10.1137\/18M1168753","volume":"32","author":"M Grohe","year":"2018","unstructured":"Grohe, M., Kreutzer, S., Rabinovich, R., Siebertz, S., Stavropoulos, K.: Coloring and covering nowhere dense graphs. SIAM J. Discrete Math. 32(4), 2467\u20132481 (2018). arXiv:1602.05926","journal-title":"SIAM J. Discrete Math."},{"key":"168_CR22","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1016\/j.ejc.2017.06.019","volume":"66","author":"J.v.d Heuvel","year":"2017","unstructured":"Heuvel, J..v.d, Mendez, P..O..d, Quiroz, D., Rabinovich, R., Siebertz, S.: On the generalised colouring numbers of graphs that exclude a fixed minor. European J. Combin. 66, 129\u2013144 (2017). arXiv:1602.09052","journal-title":"European J. Combin."},{"key":"168_CR23","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1112\/jlms.12127","volume":"98","author":"J.v.d. Heuvel","year":"2018","unstructured":"Heuvel, J..v.d., Wood, D..R.: Improper colourings inspired by Hadwiger\u2019s conjecture. J. London Math. Soc. 98, 129\u2013148 (2018). arXiv:1704.06536","journal-title":"J. London Math. Soc."},{"issue":"3","key":"168_CR24","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1007\/s00493-021-4592-8","volume":"42","author":"T Huynh","year":"2022","unstructured":"Huynh, T., Joret, G., Micek, P., Seweryn, M.T., Wollan, P.: Excluding a ladder. Combinatorica 42(3), 405\u2013432 (2022). arXiv:2002.00496","journal-title":"Combinatorica"},{"key":"168_CR25","doi-asserted-by":"publisher","first-page":"1233","DOI":"10.1090\/btran\/192","volume":"11","author":"F Illingworth","year":"2024","unstructured":"Illingworth, F., Scott, A., Wood, D.R.: Product structure of graphs with an excluded minor. Trans. Amer. Math. Soc. Ser. B 11, 1233\u20131248 (2024). arXiv:2104.06627","journal-title":"Trans. Amer. Math. Soc. Ser. B"},{"issue":"1\u20133","key":"168_CR26","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1016\/j.disc.2004.07.007","volume":"287","author":"Ken-ichi Kawarabayashi","year":"2004","unstructured":"Kawarabayashi, Ken-ichi: Rooted minor problems in highly connected graphs. Discrete Math. 287(1\u20133), 121\u2013123 (2004)","journal-title":"Discrete Math."},{"key":"168_CR27","doi-asserted-by":"publisher","first-page":"467","DOI":"10.1007\/s00493-024-00081-8","volume":"44","author":"C-H Liu","year":"2024","unstructured":"Liu, C.-H.: Defective coloring is perfect for minors. Combinatorica 44, 467\u2013507 (2024). arXiv:2208.10729","journal-title":"Combinatorica"},{"key":"168_CR28","doi-asserted-by":"crossref","unstructured":"Liu, C..-H., Oum, S..-il: Partitioning $$H$$-minor free graphs into three subgraphs with no large components. J. Combin. Theory, Series B 128, 114\u2013133 (2018). arXiv:1503.08371","DOI":"10.1016\/j.jctb.2017.08.003"},{"key":"168_CR29","unstructured":"Liu, C.-H.., Wood, D.R.: Clustered coloring of graphs excluding a subgraph and a minor, 2019. arXiv:1905.09495"},{"key":"168_CR30","unstructured":"Liu, C.-H., Wood, D.R.: Clustered graph coloring and layered treewidth, 2019. arXiv:1905.08969"},{"key":"168_CR31","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/j.jctb.2021.09.002","volume":"152","author":"C.-H Liu","year":"2022","unstructured":"Liu, C..-H., Wood, D..R..: Clustered variants of Haj\u00f3s\u2019 conjecture. J. Combin. Theory, Series B 152, 27\u201354 (2022). arXiv:1908.05597","journal-title":"J. Combin. Theory, Series B"},{"key":"168_CR32","unstructured":"N., Jaroslav., de\u00a0M., Patrice O.: Sparsity - Graphs, Structures, and Algorithms, volume\u00a028 of Algorithms and combinatorics. Springer, 2012. New York"},{"issue":"6","key":"168_CR33","doi-asserted-by":"publisher","first-page":"1387","DOI":"10.1007\/s00493-019-3848-z","volume":"39","author":"S Norin","year":"2019","unstructured":"Norin, S., Scott, A., Seymour, P., Wood, D.R.: Clustered colouring in minor-closed classes. Combinatorica 39(6), 1387\u20131412 (2019). arXiv:1708.02370","journal-title":"Combinatorica"},{"issue":"2","key":"168_CR34","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1007\/s00493-018-3733-1","volume":"39","author":"P.O.de Mendez","year":"2019","unstructured":"Mendez, P..O..de, Oum, S..-il, Wood, D..R.: Defective colouring of graphs excluding a subgraph or minor. Combinatorica 39(2), 377\u2013410 (2019). arXiv:1611.09060","journal-title":"Combinatorica"},{"key":"168_CR35","unstructured":"Pilipczuk, M., Pilipczuk, M., Siebertz, S.: Lecture notes for the course \u201cSparsity\u201d given at Faculty of Mathematics, Informatics, and Mechanics of the University of Warsaw, Winter semesters 2017\/18 and 2019\/20. https:\/\/www.mimuw.edu.pl\/~mp248287\/sparsity2"},{"key":"168_CR36","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/j.jctb.2021.06.002","volume":"151","author":"M Pilipczuk","year":"2021","unstructured":"Pilipczuk, M., Siebertz, S.: Polynomial bounds for centered colorings on proper minor-closed graph classes. J. Combin. Theory, Series B 151, 111\u2013147 (2021). arXiv:1807.03683","journal-title":"J. Combin. Theory, Series B"},{"key":"168_CR37","doi-asserted-by":"crossref","unstructured":"Pilipczuk, M., Wrochna, M.: On space efficiency of algorithms working on structural decompositions of graphs. ACM Trans. Computation Theory, 9(4), 2018. arXiv:1509.05896","DOI":"10.1145\/3154856"},{"issue":"2","key":"168_CR38","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1006\/jctb.1998.1835","volume":"74","author":"Bruce A Reed","year":"1998","unstructured":"Reed, Bruce A., Seymour, Paul: Fractional colouring and Hadwiger\u2019s conjecture. J. Combin. Theory Ser. B 74(2), 147\u2013152 (1998)","journal-title":"J. Combin. Theory Ser. B"},{"issue":"1","key":"168_CR39","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/0095-8956(83)90079-5","volume":"35","author":"N Robertson","year":"1983","unstructured":"Robertson, N., Seymour, P.: Graph minors. I. Excluding a forest. J. Combin. Theory, Series B 35(1), 39\u201361 (1983)","journal-title":"J. Combin. Theory, Series B"},{"issue":"1","key":"168_CR40","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1016\/0095-8956(86)90030-4","volume":"41","author":"N Robertson","year":"1986","unstructured":"Robertson, N., Seymour, P.: Graph minors. V. Excluding a planar graph. J. Combin. Theory, Series B 41(1), 92\u2013114 (1986)","journal-title":"J. Combin. Theory, Series B"},{"issue":"1","key":"168_CR41","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1006\/jctb.1995.1006","volume":"63","author":"N Robertson","year":"1995","unstructured":"Robertson, N., Seymour, P.: Graph minors. XIII. The disjoint paths problem. J. Combin. Theory, Series B 63(1), 65\u2013110 (1995)","journal-title":"J. Combin. Theory, Series B"},{"issue":"1","key":"168_CR42","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/S0095-8956(03)00042-X","volume":"89","author":"N Robertson","year":"2003","unstructured":"Robertson, N., Seymour, P.: Graph minors. XVI. Excluding a non-planar graph. J. Combin. Theory, Series B 89(1), 43\u201376 (2003)","journal-title":"J. Combin. Theory, Series B"},{"key":"168_CR43","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1002\/jgt.22363","volume":"90","author":"A Scott","year":"2019","unstructured":"Scott, A., Seymour, P., Wood, D.R.: Bad news for chordal partitions. J. Graph Theory 90, 5\u201312 (2019). arXiv:1707.04964","journal-title":"J. Graph Theory"},{"key":"168_CR44","doi-asserted-by":"crossref","unstructured":"Wood, D.R.: Defective and clustered graph colouring. Electron. J. Combin., DS23, 2018. Version 1, https:\/\/www.combinatorics.org\/DS23","DOI":"10.37236\/7406"}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-025-00168-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00493-025-00168-w","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-025-00168-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,29]],"date-time":"2025-12-29T13:17:53Z","timestamp":1767014273000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00493-025-00168-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,11,7]]},"references-count":44,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2025,12]]}},"alternative-id":["168"],"URL":"https:\/\/doi.org\/10.1007\/s00493-025-00168-w","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"type":"print","value":"0209-9683"},{"type":"electronic","value":"1439-6912"}],"subject":[],"published":{"date-parts":[[2025,11,7]]},"assertion":[{"value":"4 February 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 May 2025","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 June 2025","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 November 2025","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"62"}}