{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,17]],"date-time":"2026-01-17T07:14:02Z","timestamp":1768634042253,"version":"3.49.0"},"reference-count":26,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2022,7,5]],"date-time":"2022-07-05T00:00:00Z","timestamp":1656979200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2023,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The <jats:italic>clustered chromatic number<\/jats:italic> of a class of graphs is the minimum integer <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000165_inline1.png\"\/><jats:tex-math>\n$k$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> such that for some integer <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000165_inline2.png\"\/><jats:tex-math>\n$c$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> every graph in the class is <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000165_inline3.png\"\/><jats:tex-math>\n$k$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-colourable with monochromatic components of size at most <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000165_inline4.png\"\/><jats:tex-math>\n$c$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. We determine the clustered chromatic number of any minor-closed class with bounded treedepth, and prove a best possible upper bound on the clustered chromatic number of any minor-closed class with bounded pathwidth. As a consequence, we determine the fractional clustered chromatic number of every minor-closed class.<\/jats:p>","DOI":"10.1017\/s0963548322000165","type":"journal-article","created":{"date-parts":[[2022,7,5]],"date-time":"2022-07-05T07:11:24Z","timestamp":1657005084000},"page":"122-133","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":4,"title":["Clustered colouring of graph classes with bounded treedepth or pathwidth"],"prefix":"10.1017","volume":"32","author":[{"given":"Sergey","family":"Norin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alex","family":"Scott","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David R.","family":"Wood","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2022,7,5]]},"reference":[{"key":"S0963548322000165_ref4","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1002\/jgt.22418","article-title":"Improper coloring of graphs on surfaces","volume":"91","author":"Choi","year":"2019","journal-title":"J. Graph Theory"},{"key":"S0963548322000165_ref10","doi-asserted-by":"publisher","DOI":"10.1016\/S0095-8956(03)00031-5"},{"key":"S0963548322000165_ref16","unstructured":"[16] Liu, C.-H. and Wood, D. R. (2019b) Clustered graph coloring and layered treewidth, arXiv: 1905.08969."},{"key":"S0963548322000165_ref17","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/j.jctb.2021.09.002","article-title":"Clustered variants of Haj\u00f3s\u2019 conjecture","volume":"152","author":"Liu","year":"2022","journal-title":"J. Combin. Theory, Ser. B"},{"key":"S0963548322000165_ref21","doi-asserted-by":"publisher","DOI":"10.1112\/jlms.12127"},{"key":"S0963548322000165_ref22","doi-asserted-by":"crossref","DOI":"10.37236\/7406","article-title":"Defective and clustered graph colouring","author":"Wood","year":"2018","journal-title":"Electron. J. Combin.,"},{"key":"S0963548322000165_ref24","volume-title":"11011110.","author":"Eppstein","year":"2020"},{"key":"S0963548322000165_ref9","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":"Combin., Probab. Comput."},{"key":"S0963548322000165_ref25","doi-asserted-by":"crossref","first-page":"661","DOI":"10.1007\/s00493-015-3070-6","article-title":"Nonrepetitive colouring via entropy compression","volume":"36","author":"Dujmovi\u0107","year":"2016","journal-title":"Combinatorica"},{"key":"S0963548322000165_ref7","unstructured":"[7] Dvo\u0159\u00e1k, Z. and Norin, S. (2017) Islands in minor-closed classes. I. Bounded treewidth and separators, arXiv: 1710.02727."},{"key":"S0963548322000165_ref26","doi-asserted-by":"publisher","DOI":"10.37236\/8909"},{"key":"S0963548322000165_ref3","first-page":"411","article-title":"Bounded monochromatic components for random graphs","volume":"9","author":"Broutin","year":"2018","journal-title":"J. Comb."},{"key":"S0963548322000165_ref5","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1002\/(SICI)1097-0118(199703)24:3<205::AID-JGT2>3.0.CO;2-T","article-title":"Defective coloring revisited","volume":"24","author":"Cowen","year":"1997","journal-title":"J. Graph Theory"},{"key":"S0963548322000165_ref12","doi-asserted-by":"crossref","first-page":"815","DOI":"10.1017\/S0963548308009462","article-title":"A weakening of the odd Hadwiger\u2019s conjecture","volume":"17","author":"Kawarabayashi","year":"2008","journal-title":"Combin. Probab. Comput."},{"key":"S0963548322000165_ref23","doi-asserted-by":"crossref","unstructured":"[23] Ne\u0161et\u0159il, J. and Ossona de Mendez, P. (2012) Sparsity, vol. 28. Algorithms and Combinatorics. Springer.","DOI":"10.1007\/978-3-642-27875-4"},{"key":"S0963548322000165_ref19","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-019-3848-z"},{"key":"S0963548322000165_ref11","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548318000548"},{"key":"S0963548322000165_ref1","doi-asserted-by":"publisher","DOI":"10.1016\/S0095-8956(02)00006-0"},{"key":"S0963548322000165_ref18","first-page":"236","article-title":"Colourings with bounded monochromatic components in graphs of given circumference","volume":"69","author":"Mohar","year":"2017","journal-title":"Australas. J. Combin."},{"key":"S0963548322000165_ref8","doi-asserted-by":"publisher","DOI":"10.1137\/141002177"},{"key":"S0963548322000165_ref6","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548321000213"},{"key":"S0963548322000165_ref14","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2017.08.003"},{"key":"S0963548322000165_ref15","unstructured":"[15] Liu, C.-H. and Wood, D. R. (2019a) Clustered coloring of graphs excluding a subgraph and a minor , arXiv: 1905.09495."},{"key":"S0963548322000165_ref20","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-018-3733-1"},{"key":"S0963548322000165_ref2","doi-asserted-by":"crossref","first-page":"517","DOI":"10.1002\/jgt.3190110408","article-title":"A note on defective colorings of graphs in surfaces","volume":"11","author":"Archdeacon","year":"1987","journal-title":"J. Graph Theory"},{"key":"S0963548322000165_ref13","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2006.11.002"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548322000165","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,20]],"date-time":"2022-12-20T05:08:21Z","timestamp":1671512901000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548322000165\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,5]]},"references-count":26,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,1]]}},"alternative-id":["S0963548322000165"],"URL":"https:\/\/doi.org\/10.1017\/s0963548322000165","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,7,5]]},"assertion":[{"value":"\u00a9 The Author(s), 2022. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}}]}}