{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,29]],"date-time":"2025-12-29T13:51:11Z","timestamp":1767016271376,"version":"3.40.5"},"reference-count":81,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2023,12,7]],"date-time":"2023-12-07T00:00:00Z","timestamp":1701907200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2024,5]]},"abstract":"Abstract<\/jats:title>We show that many graphs with bounded treewidth can be described as subgraphs of the strong product of a graph with smaller treewidth and a bounded-size complete graph. To this end, define the underlying treewidth<\/jats:italic> of a graph class \n$\\mathcal{G}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> to be the minimum non-negative integer \n$c$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> such that, for some function \n$f$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, for every graph \n$G \\in \\mathcal{G}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> there is a graph \n$H$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> with \n$\\textrm{tw}(H) \\leqslant c$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> such that \n$G$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> is isomorphic to a subgraph of \n$H \\boxtimes K_{f(\\textrm{tw}(G))}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. We introduce disjointed coverings of graphs and show they determine the underlying treewidth of any graph class. Using this result, we prove that the class of planar graphs has underlying treewidth \n$3$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>; the class of \n$K_{s,t}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-minor-free graphs has underlying treewidth \n$s$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> (for \n$t \\geqslant \\max \\{s,3\\}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>); and the class of \n$K_t$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-minor-free graphs has underlying treewidth \n$t-2$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. In general, we prove that a monotone class has bounded underlying treewidth if and only if it excludes some fixed topological minor. We also study the underlying treewidth of graph classes defined by an excluded subgraph or excluded induced subgraph. We show that the class of graphs with no \n$H$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> subgraph has bounded underlying treewidth if and only if every component of \n$H$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> is a subdivided star, and that the class of graphs with no induced \n$H$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> subgraph has bounded underlying treewidth if and only if every component of \n$H$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> is a star.<\/jats:p>","DOI":"10.1017\/s0963548323000457","type":"journal-article","created":{"date-parts":[[2023,12,7]],"date-time":"2023-12-07T05:23:26Z","timestamp":1701926606000},"page":"351-376","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":8,"title":["Product structure of graph classes with bounded treewidth"],"prefix":"10.1017","volume":"33","author":[{"given":"Rutger","family":"Campbell","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2653-9576","authenticated-orcid":false,"given":"Katie","family":"Clinch","sequence":"additional","affiliation":[]},{"given":"Marc","family":"Distel","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2095-7101","authenticated-orcid":false,"given":"J. Pascal","family":"Gollin","sequence":"additional","affiliation":[]},{"given":"Kevin","family":"Hendrey","sequence":"additional","affiliation":[]},{"given":"Robert","family":"Hickingbotham","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6908-923X","authenticated-orcid":false,"given":"Tony","family":"Huynh","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5350-2379","authenticated-orcid":false,"given":"Freddie","family":"Illingworth","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8890-683X","authenticated-orcid":false,"given":"Youri","family":"Tamitegama","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0536-0374","authenticated-orcid":false,"given":"Jane","family":"Tan","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8866-3041","authenticated-orcid":false,"given":"David R.","family":"Wood","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2023,12,7]]},"reference":[{"key":"S0963548323000457_ref28","article-title":"Planar graphs have bounded nonrepetitive chromatic number","volume":"5","author":"Dujmovi\u0107","year":"2020","journal-title":"Adv. Comb."},{"key":"S0963548323000457_ref2","doi-asserted-by":"crossref","first-page":"R99","DOI":"10.37236\/823","article-title":"Notes on nonrepetitive graph colouring","volume":"15","author":"Bar\u00e1t","year":"2008","journal-title":"Electron. J. Comb."},{"key":"S0963548323000457_ref49","doi-asserted-by":"crossref","first-page":"3517","DOI":"10.1016\/j.disc.2012.08.004","article-title":"On \n\n\n\n$K_{s,t}$\n\n\n-minors in graphs with given average degree, II","volume":"312","year":"2012","journal-title":"Discrete Math."},{"key":"S0963548323000457_ref33","first-page":"38:1","volume-title":"Proc. 38th Int\u2019l Symp. on Computat. Geometry (SoCG 2022)","author":"Dvor\u00e1k","year":"2022"},{"key":"S0963548323000457_ref32","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/j.comgeo.2006.08.002","article-title":"Graph drawings with few slopes","volume":"38","author":"Dujmovi\u0107","year":"2007","journal-title":"Comput. Geom. Theory Appl."},{"key":"S0963548323000457_ref78","doi-asserted-by":"crossref","first-page":"P3.18","DOI":"10.37236\/5715","article-title":"Cliques in graphs excluding a complete graph minor","volume":"23","author":"Wood","year":"2016","journal-title":"Electron. J. Comb."},{"key":"S0963548323000457_ref44","first-page":"353","volume-title":"38th Annual Symp. on Foundations of Computer Science (FOCS \u201997)","author":"Kleinberg","year":"1997"},{"key":"S0963548323000457_ref30","doi-asserted-by":"crossref","first-page":"553","DOI":"10.1137\/S0097539702416141","article-title":"Layout of graphs with bounded tree-width","volume":"34","author":"Dujmovi\u0107","year":"2005","journal-title":"SIAM J. Comput."},{"key":"S0963548323000457_ref13","doi-asserted-by":"crossref","first-page":"R107","DOI":"10.37236\/831","article-title":"Distinct distances in graph drawings","volume":"15","author":"Carmi","year":"2008","journal-title":"Electron. J. Combin."},{"key":"S0963548323000457_ref39","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1016\/0012-365X(91)90436-6","article-title":"Tree-partitions of infinite graphs","volume":"97","author":"Halin","year":"1991","journal-title":"Discrete Math."},{"key":"S0963548323000457_ref26","unstructured":"[26] Dragani\u0107, N. , Kaufmann, M. , Correia, D. M. , Petrova, K. and Steiner, R. (2023) Size-Ramsey numbers of structurally sparse graphs. arXiv:2307.12028."},{"key":"S0963548323000457_ref29","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1145\/3385731","article-title":"Planar graphs have bounded queue-number","volume":"67","author":"Dujmovi\u0107","year":"2020","journal-title":"J. ACM"},{"key":"S0963548323000457_ref21","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s004930050001","article-title":"Partitioning graphs of bounded tree-width","volume":"18","author":"Ding","year":"1998","journal-title":"Combinatorica"},{"key":"S0963548323000457_ref66","first-page":"125","volume-title":"Graph Structure Theory. Proc. AMS-IMS-SIAM Joint Summer Research Conf. on Graph Minors","author":"Robertson","year":"1993"},{"key":"S0963548323000457_ref45","first-page":"37","article-title":"The minimum Hadwiger number for graphs with a given mean degree of vertices","volume":"38","author":"Kostochka","year":"1982","journal-title":"Metody Diskret. Analiz."},{"key":"S0963548323000457_ref7","first-page":"141","article-title":"A note on domino treewidth","volume":"3","author":"Bodlaender","year":"1999","journal-title":"Discrete Math. Theor. Comput. Sci."},{"key":"S0963548323000457_ref15","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1016\/j.jctb.2003.09.001","article-title":"Excluding any graph as a minor allows a low tree-width 2-coloring","volume":"91","author":"DeVos","year":"2004","journal-title":"J. Combin. Theory Ser. B"},{"key":"S0963548323000457_ref58","doi-asserted-by":"crossref","first-page":"1387","DOI":"10.1007\/s00493-019-3848-z","article-title":"Clustered colouring in minor-closed classes","volume":"39","author":"Norin","year":"2019","journal-title":"Combinatorica"},{"key":"S0963548323000457_ref4","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1016\/0020-0190(88)90051-8","article-title":"The complexity of finding uniform emulations on fixed graphs","volume":"29","author":"Bodlaender","year":"1988","journal-title":"Inf. Process. Lett."},{"key":"S0963548323000457_ref8","doi-asserted-by":"crossref","first-page":"94","DOI":"10.1006\/jagm.1996.0854","article-title":"Domino treewidth","volume":"24","author":"Bodlaender","year":"1997","journal-title":"J. Algorithms"},{"key":"S0963548323000457_ref24","unstructured":"[24] Distel, M. and Wood, D. R. (2022) Tree-partitions with bounded degree trees. arXiv:2210.12577. 2021-22 MATRIX Annals, to appear."},{"key":"S0963548323000457_ref18","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1016\/j.dam.2004.01.010","article-title":"Graph minor hierarchies","volume":"145","author":"Diestel","year":"2005","journal-title":"Discrete Appl. Math."},{"key":"S0963548323000457_ref54","doi-asserted-by":"crossref","first-page":"103517","DOI":"10.1016\/j.ejc.2022.103517","article-title":"Tree-width dichotomy","volume":"103","author":"Lozin","year":"2022","journal-title":"Eur. J. Comb."},{"key":"S0963548323000457_ref46","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1007\/BF02579141","article-title":"Lower bound of the Hadwiger number of graphs by their average degree","volume":"4","author":"Kostochka","year":"1984","journal-title":"Combinatorica"},{"key":"S0963548323000457_ref14","doi-asserted-by":"crossref","first-page":"1330","DOI":"10.1007\/s00453-017-0313-5","article-title":"An O(log OPT)-approximation for covering and packing minor models of \n\n\n\n$\\theta _r$","volume":"80","author":"Chatzidimitriou","year":"2018","journal-title":"Algorithmica"},{"key":"S0963548323000457_ref31","doi-asserted-by":"crossref","first-page":"34","DOI":"10.1016\/j.jctb.2023.03.004","article-title":"Graph product structure for non-minor-closed classes","volume":"162","author":"Dujmovi\u0107","year":"2023","journal-title":"J. Combin. Theory Ser. B"},{"key":"S0963548323000457_ref11","unstructured":"[11] \u00c9douard Bonnet, O.-J. K. and Wood, D. R. (2022) Reduced bandwidth: A qualitative strengthening of twin-width in minor-closed classes (and beyond). arXiv:2202.11858."},{"key":"S0963548323000457_ref52","doi-asserted-by":"crossref","first-page":"38","DOI":"10.1016\/j.jctb.2014.09.003","article-title":"Tree-width and planar minors","volume":"111","author":"Leaf","year":"2015","journal-title":"J. Combin. Theory Ser. B"},{"volume-title":"Graph Theory","year":"2018","author":"Diestel","key":"S0963548323000457_ref17"},{"key":"S0963548323000457_ref50","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/j.ejc.2004.02.002","article-title":"Forcing unbalanced complete bipartite minors","volume":"26","author":"K\u00fchn","year":"2005","journal-title":"Eur. J. Comb."},{"key":"S0963548323000457_ref57","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-27875-4","volume-title":"Sparsity","author":"Ne\u0161et\u0159il","year":"2012"},{"key":"S0963548323000457_ref20","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1016\/0012-365X(94)00337-I","article-title":"On tree-partitions of graphs","volume":"149","author":"Ding","year":"1996","journal-title":"Discrete Math."},{"key":"S0963548323000457_ref25","article-title":"Improved bounds for centered colorings","volume":"8","author":"D\u00f6cebski","year":"2021","journal-title":"Adv. Comb."},{"key":"S0963548323000457_ref61","doi-asserted-by":"crossref","first-page":"300","DOI":"10.1017\/S0963548315000073","article-title":"Forcing a sparse minor","volume":"25","author":"Reed","year":"2016","journal-title":"Comb. Probab. Comput"},{"key":"S0963548323000457_ref56","doi-asserted-by":"crossref","DOI":"10.56021\/9780801866890","volume-title":"Graphs on Surfaces","author":"Mohar","year":"2001"},{"key":"S0963548323000457_ref6","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0304-3975(97)00228-4","article-title":"A partial \n\n\n\n$k$\n\n\n-arboretum of graphs with bounded treewidth","volume":"209","author":"Bodlaender","year":"1998","journal-title":"Theor. Comput. Sci."},{"key":"S0963548323000457_ref69","doi-asserted-by":"crossref","first-page":"412","DOI":"10.1007\/BFb0028825","volume-title":"Proc. Int\u2019l Conf. on Fundamentals of Computation Theory","author":"Seese","year":"1985"},{"key":"S0963548323000457_ref71","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1017\/S0305004100061521","article-title":"An extremal function for contractions of graphs","volume":"95","author":"Thomason","year":"1984","journal-title":"Math. Proc. Cambridge Philos. Soc."},{"key":"S0963548323000457_ref68","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1002\/jgt.22363","article-title":"Bad news for chordal partitions","volume":"90","author":"Scott","year":"2019","journal-title":"J. Graph Theory"},{"key":"S0963548323000457_ref37","doi-asserted-by":"crossref","first-page":"288","DOI":"10.1109\/TC.1982.1675994","article-title":"Quotient networks","volume":"C-31","author":"Fishburn","year":"1982","journal-title":"IEEE Trans. Comput."},{"key":"S0963548323000457_ref72","doi-asserted-by":"crossref","first-page":"318","DOI":"10.1006\/jctb.2000.2013","article-title":"The extremal function for complete minors","volume":"81","author":"Thomason","year":"2001","journal-title":"J. Combin. Theory Ser. B"},{"key":"S0963548323000457_ref47","doi-asserted-by":"crossref","first-page":"4435","DOI":"10.1016\/j.disc.2007.08.041","article-title":"On \n\n\n\n$K_{s,t}$\n\n\n-minors in graphs with given average degree","volume":"308","year":"2008","journal-title":"Discrete Math."},{"key":"S0963548323000457_ref74","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1016\/j.ejc.2017.06.019","article-title":"On the generalised colouring numbers of graphs that exclude a fixed minor","volume":"66","author":"van den Heuvel","year":"2017","journal-title":"Eur. J. Comb."},{"key":"S0963548323000457_ref76","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1002\/jgt.20183","article-title":"Vertex partitions of chordal graphs","volume":"53","author":"Wood","year":"2006","journal-title":"J. Graph Theory"},{"key":"S0963548323000457_ref10","doi-asserted-by":"crossref","first-page":"883","DOI":"10.1006\/eujc.1997.0188","article-title":"Proof of a conjecture of Mader, Erd\u0151s and Hajnal on topological complete subgraphs","volume":"19","author":"Bollob\u00e1s","year":"1998","journal-title":"Eur. J. Comb."},{"key":"S0963548323000457_ref64","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/0095-8956(84)90013-3","article-title":"Graph minors. III. Planar tree-width","volume":"36","author":"Robertson","year":"1984","journal-title":"J. Combin. Theory Ser. B"},{"key":"S0963548323000457_ref81","unstructured":"[81] Zhang, R.-R. and Amini, M.-R. (2022) Generalization bounds for learning under graph-dependence: A survey. arXiv:2203.13534."},{"key":"S0963548323000457_ref1","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1016\/S0095-8956(02)00006-0","article-title":"Partitioning into graphs with only small components","volume":"87","author":"Alon","year":"2003","journal-title":"J. Combin. Theory Ser. B"},{"key":"S0963548323000457_ref34","doi-asserted-by":"crossref","first-page":"148","DOI":"10.1007\/BF01933740","article-title":"Quotient tree partitioning of undirected graphs","volume":"26","author":"Edenbrandt","year":"1986","journal-title":"BIT"},{"key":"S0963548323000457_ref67","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1006\/jctb.1995.1032","article-title":"Sachs\u2019 linkless embedding conjecture","volume":"64","author":"Robertson","year":"1995","journal-title":"J. Combin. Theory Series B"},{"key":"S0963548323000457_ref23","first-page":"6","article-title":"Improved product structure for graphs on surfaces","volume":"24","author":"Distel","year":"2022","journal-title":"Discrete Math. Theor. Comput. Sci."},{"journal-title":"SIAM J. Discrete Math.","article-title":"Shallow minors, graph products and beyond planar graphs","author":"Hickingbotham","key":"S0963548323000457_ref41"},{"key":"S0963548323000457_ref48","doi-asserted-by":"crossref","first-page":"2637","DOI":"10.1016\/j.disc.2010.03.026","article-title":"Dense graphs have \n\n\n\n$K_{3,t}$\n\n\n minors","volume":"310","year":"2010","journal-title":"Discrete Math."},{"key":"S0963548323000457_ref65","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","article-title":"Graph minors. II. Algorithmic aspects of tree-width","volume":"7","author":"Robertson","year":"1986","journal-title":"J. Algorithms"},{"key":"S0963548323000457_ref70","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1016\/j.ejc.2004.02.013","article-title":"An improved linear edge bound for graph linkages","volume":"26","author":"Thomas","year":"2005","journal-title":"Eur. J. Comb."},{"key":"S0963548323000457_ref5","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1016\/0890-5401(90)90027-F","article-title":"The complexity of finding uniform emulations on paths and ring networks","volume":"86","author":"Bodlaender","year":"1990","journal-title":"Inf. Comput."},{"key":"S0963548323000457_ref40","doi-asserted-by":"crossref","first-page":"364","DOI":"10.1002\/jgt.22030","article-title":"Parameters tied to treewidth","volume":"84","author":"Harvey","year":"2017","journal-title":"J. Graph Theory"},{"key":"S0963548323000457_ref63","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1006\/jctb.1998.1835","article-title":"Fractional colouring and Hadwiger\u2019s conjecture","volume":"74","author":"Reed","year":"1998","journal-title":"J. Combin. Theory Ser. B"},{"key":"S0963548323000457_ref75","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1112\/jlms.12127","article-title":"Improper colourings inspired by Hadwiger\u2019s conjecture","volume":"98","author":"van den Heuvel","year":"2018","journal-title":"J. Lond. Math. Soc."},{"key":"S0963548323000457_ref59","doi-asserted-by":"crossref","first-page":"377","DOI":"10.1007\/s00493-018-3733-1","article-title":"Defective colouring of graphs excluding a subgraph or minor","volume":"39","author":"de Mendez","year":"2019","journal-title":"Combinatorica"},{"key":"S0963548323000457_ref12","unstructured":"[12] Campbell, R. , K. Clinch, M. Distel, J. P. Gollin, K. Hendrey, R. Hickingbotham, T. Huynh, F. Illingworth, Y. Tamitegama, J. Tan and D. R. Wood (2022) Product structure of graph classes with bounded treewidth. arXiv:2206.02395."},{"key":"S0963548323000457_ref80","first-page":"117","article-title":"Planar decompositions and the crossing number of graphs with an excluded minor","volume":"13","author":"Wood","year":"2007","journal-title":"N. Y. J. Math."},{"key":"S0963548323000457_ref19","doi-asserted-by":"crossref","first-page":"481","DOI":"10.1002\/jgt.3190200412","article-title":"Some results on tree decomposition of graphs","volume":"20","author":"Ding","year":"1995","journal-title":"J. Graph Theory"},{"key":"S0963548323000457_ref60","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1016\/j.dam.2016.12.025","article-title":"Recent techniques and results on the Erd\u0151s-P\u00f3sa property","volume":"231","author":"Raymond","year":"2017","journal-title":"Discrete Appl. Math."},{"key":"S0963548323000457_ref43","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1137\/20M1335790","article-title":"The size Ramsey number of graphs with bounded treewidth","volume":"35","author":"Kamcev","year":"2021","journal-title":"SIAM J. Discrete Math."},{"key":"S0963548323000457_ref55","article-title":"Moore graphs and beyond: A survey of the degree\/diameter problem","volume":"DS14","author":"Miller","year":"2013","journal-title":"Electron. J. Comb."},{"key":"S0963548323000457_ref73","doi-asserted-by":"crossref","first-page":"P2.51","DOI":"10.37236\/10614","article-title":"An improved planar graph product structure theorem","volume":"29","author":"Ueckerdt","year":"2022","journal-title":"Electron. J. Comb."},{"key":"S0963548323000457_ref16","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1016\/j.comgeo.2004.11.003","article-title":"Computing straight-line 3D grid drawings of graphs in linear volume","volume":"32","author":"Di Giacomo","year":"2005","journal-title":"Comput. Geom. Theory Appl."},{"key":"S0963548323000457_ref38","doi-asserted-by":"crossref","first-page":"74","DOI":"10.1007\/978-3-662-53536-3_7","volume-title":"Proc. 42nd Int\u2019l Workshop on Graph-Theoretic Concepts in Computer Science (WG 2016)","author":"Giannopoulou","year":"2016"},{"key":"S0963548323000457_ref51","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1016\/j.apal.2004.06.002","article-title":"Logical aspects of Cayley-graphs: the group case","volume":"131","author":"Kuske","year":"2005","journal-title":"Ann. Pure Appl. Logic"},{"key":"S0963548323000457_ref3","first-page":"23:1","volume-title":"Proc. 33rd Int\u2019l Symp. on Algorithms and Computation (ISAAC \u201922)","author":"Bekos","year":"2022"},{"key":"S0963548323000457_ref35","doi-asserted-by":"crossref","first-page":"551","DOI":"10.1017\/S0963548314000170","article-title":"Colouring planar graphs with three colours and no large monochromatic components","volume":"23","author":"Esperet","year":"2014","journal-title":"Comb. Probab. Comput."},{"key":"S0963548323000457_ref62","first-page":"85","volume-title":"Recent Advances in Algorithms and Combinatorics","author":"Reed","year":"2003"},{"key":"S0963548323000457_ref27","doi-asserted-by":"crossref","first-page":"42","DOI":"10.1145\/3477542","article-title":"Adjacency labelling for planar graphs (and beyond)","volume":"68","author":"Dujmovi\u0107","year":"2021","journal-title":"J. ACM"},{"key":"S0963548323000457_ref53","unstructured":"[53] Liu, C.-H. and Wood, D. R. (2019) Clustered graph coloring and layered treewidth. arXiv:1905.08969."},{"key":"S0963548323000457_ref36","doi-asserted-by":"crossref","first-page":"1333","DOI":"10.1112\/jlms.12781","article-title":"Sparse universal graphs for planarity","volume":"108","author":"Esperet","year":"2023","journal-title":"J. Lond. Math. Soc."},{"key":"S0963548323000457_ref77","doi-asserted-by":"crossref","first-page":"1245","DOI":"10.1016\/j.ejc.2008.11.010","article-title":"On tree-partition-width","volume":"30","author":"Wood","year":"2009","journal-title":"Eur. J. Comb."},{"key":"S0963548323000457_ref9","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1016\/S0019-9958(86)80008-0","article-title":"Simulation of large networks on smaller networks","volume":"71","author":"Bodlaender","year":"1986","journal-title":"Inf. Control"},{"key":"S0963548323000457_ref42","unstructured":"[42] Huynh, T. , Mohar, B. , \u0160\u00e1mal, R. , Thomassen, C. and Wood, D. R. (2021) Universality in minor-closed graph classes. arXiv:2109.00327."},{"key":"S0963548323000457_ref79","article-title":"Defective and clustered graph colouring","volume":"DS23","author":"Wood","year":"2018","journal-title":"Electron. J. Comb."},{"key":"S0963548323000457_ref22","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1006\/jctb.2000.1962","article-title":"Surfaces, tree-width, clique-minors, and partitions","volume":"79","author":"Ding","year":"2000","journal-title":"J. Combin. Theory Ser. B"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548323000457","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,5]],"date-time":"2024-04-05T10:18:32Z","timestamp":1712312312000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548323000457\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12,7]]},"references-count":81,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,5]]}},"alternative-id":["S0963548323000457"],"URL":"https:\/\/doi.org\/10.1017\/s0963548323000457","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"type":"print","value":"0963-5483"},{"type":"electronic","value":"1469-2163"}],"subject":[],"published":{"date-parts":[[2023,12,7]]},"assertion":[{"value":"\u00a9 The Author(s), 2023. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (https:\/\/creativecommons.org\/licenses\/by\/4.0\/), which permits unrestricted re-use, distribution, and reproduction in any medium, provided the original work is properly cited.","name":"license","label":"License","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}