{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,29]],"date-time":"2025-12-29T13:45:10Z","timestamp":1767015910118},"reference-count":55,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2021,6,18]],"date-time":"2021-06-18T00:00:00Z","timestamp":1623974400000},"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":[[2022,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A (not necessarily proper) vertex colouring of a graph has<jats:italic>clustering c<\/jats:italic>if every monochromatic component has at most<jats:italic>c<\/jats:italic>vertices. We prove that planar graphs with maximum degree<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548321000213_inline1.png\" \/><jats:tex-math>$\\Delta$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>are 3-colourable with clustering<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548321000213_inline2.png\" \/><jats:tex-math>$O(\\Delta^2)$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. The previous best bound was<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548321000213_inline3.png\" \/><jats:tex-math>$O(\\Delta^{37})$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. This result for planar graphs generalises to graphs that can be drawn on a surface of bounded Euler genus with a bounded number of crossings per edge. We then prove that graphs with maximum degree<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548321000213_inline4.png\" \/><jats:tex-math>$\\Delta$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>that exclude a fixed minor are 3-colourable with clustering<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548321000213_inline5.png\" \/><jats:tex-math>$O(\\Delta^5)$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. The best previous bound for this result was exponential in<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548321000213_inline6.png\" \/><jats:tex-math>$\\Delta$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>.<\/jats:p>","DOI":"10.1017\/s0963548321000213","type":"journal-article","created":{"date-parts":[[2021,6,18]],"date-time":"2021-06-18T10:47:50Z","timestamp":1624013270000},"page":"123-135","update-policy":"http:\/\/dx.doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":10,"title":["Clustered 3-colouring graphs of bounded degree"],"prefix":"10.1017","volume":"31","author":[{"given":"Vida","family":"Dujmovi\u0107","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Louis","family":"Esperet","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pat","family":"Morin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bartosz","family":"Walczak","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":[[2021,6,18]]},"reference":[{"key":"S0963548321000213_ref33","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548318000548"},{"key":"S0963548321000213_ref4","doi-asserted-by":"publisher","DOI":"10.1145\/174644.174650"},{"key":"S0963548321000213_ref11","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2004.01.010"},{"key":"S0963548321000213_ref32","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548319000063"},{"key":"S0963548321000213_ref27","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.124"},{"key":"S0963548321000213_ref53","doi-asserted-by":"publisher","DOI":"10.1112\/jlms.12127"},{"key":"S0963548321000213_ref21","unstructured":"[21] Dvo\u0159\u00e1k, Z. and Norin, S. (2017) Islands in minor-closed classes. I. Bounded treewidth and separators. arXiv:1710.02727."},{"key":"S0963548321000213_ref52","unstructured":"[52] Shahrokhi, F. (2013) New representation results for planar graphs. In Proceedings of the 29th European Workshop on Computational Geometry (EuroCG 2013), pp. 177\u2013180. arXiv:1502.06175."},{"key":"S0963548321000213_ref2","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-1990-1065053-0"},{"key":"S0963548321000213_ref25","unstructured":"[25] Esperet, L. , Joret, G. and Morin, P. (2020) Sparse universal graphs for planarity. arXiv:2010.05779."},{"key":"S0963548321000213_ref37","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2017.08.003"},{"key":"S0963548321000213_ref18","first-page":"22","article-title":"2020 b) Planar graphs have bounded queue-number","volume":"67","author":"Dujmovi\u0107","journal-title":"J. ACM"},{"key":"S0963548321000213_ref20","unstructured":"[20] Dujmovi\u0107, V. , Morin, P. and Wood, D. R. (2019) Graph product structure for non-minor-closed classes. arXiv:1907.05168."},{"key":"S0963548321000213_ref10","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.136"},{"key":"S0963548321000213_ref44","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-019-3848-z"},{"key":"S0963548321000213_ref19","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2017.05.006"},{"key":"S0963548321000213_ref29","doi-asserted-by":"publisher","DOI":"10.1007\/BF01917434"},{"key":"S0963548321000213_ref8","doi-asserted-by":"publisher","DOI":"10.1145\/506147.506148"},{"key":"S0963548321000213_ref22","doi-asserted-by":"publisher","DOI":"10.1137\/141002177"},{"key":"S0963548321000213_ref42","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":"S0963548321000213_ref50","doi-asserted-by":"publisher","DOI":"10.1016\/S0095-8956(03)00042-X"},{"key":"S0963548321000213_ref39","unstructured":"[39] Liu, C.-H. and Wood, D. R. (2019 b) Clustered graph coloring and layered treewidth. arXiv:1905.08969."},{"key":"S0963548321000213_ref12","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190200412"},{"key":"S0963548321000213_ref14","doi-asserted-by":"publisher","DOI":"10.1137\/16M1062879"},{"key":"S0963548321000213_ref49","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90023-4"},{"key":"S0963548321000213_ref5","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-018-0487-5"},{"key":"S0963548321000213_ref9","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22418"},{"key":"S0963548321000213_ref7","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.27"},{"key":"S0963548321000213_ref51","doi-asserted-by":"publisher","DOI":"10.1090\/tran\/7962"},{"key":"S0963548321000213_ref3","volume-title":"Vol. 98 of Contemporary Mathematics","author":"Appel","year":"1989"},{"key":"S0963548321000213_ref35","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548308009140"},{"key":"S0963548321000213_ref46","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511662119.006"},{"key":"S0963548321000213_ref26","doi-asserted-by":"publisher","DOI":"10.1137\/140957883"},{"key":"S0963548321000213_ref16","doi-asserted-by":"publisher","DOI":"10.19086\/aic.12100"},{"key":"S0963548321000213_ref45","unstructured":"[45] Norin, S. , Scott, A. and Wood, D. R. (2020) Clustered colouring of graph classes with bounded treedepth or pathwidth, arXiv:2012.05554."},{"key":"S0963548321000213_ref54","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2008.11.010"},{"key":"S0963548321000213_ref48","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(84)90013-3"},{"key":"S0963548321000213_ref55","doi-asserted-by":"publisher","DOI":"10.37236\/7406"},{"key":"S0963548321000213_ref23","doi-asserted-by":"publisher","DOI":"10.1007\/s004530010020"},{"key":"S0963548321000213_ref13","doi-asserted-by":"publisher","DOI":"10.1137\/18M122162X"},{"key":"S0963548321000213_ref47","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1997.1750"},{"key":"S0963548321000213_ref15","unstructured":"[15] Dujmovi\u0107, V. , Esperet, L. , Joret, G. , Gavoille, C. , Micek, P. and Morin, P. (to appear) Adjacency labelling for planar graphs (and beyond). J. ACM. arXiv:2003.04280."},{"key":"S0963548321000213_ref34","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1997.646124"},{"key":"S0963548321000213_ref17","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00454"},{"key":"S0963548321000213_ref38","unstructured":"[38] Liu, C.-H. and Wood, D. R. (2019 a) Clustered coloring of graphs excluding a subgraph and a minor. arXiv:1905.09495."},{"key":"S0963548321000213_ref24","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548314000170"},{"key":"S0963548321000213_ref30","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22030"},{"key":"S0963548321000213_ref28","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1979.11994922"},{"key":"S0963548321000213_ref6","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00228-4"},{"key":"S0963548321000213_ref36","doi-asserted-by":"publisher","DOI":"10.1137\/0136016"},{"key":"S0963548321000213_ref41","doi-asserted-by":"publisher","DOI":"10.1137\/070684112"},{"key":"S0963548321000213_ref43","doi-asserted-by":"crossref","DOI":"10.56021\/9780801866890","volume-title":"Graphs on Surfaces","author":"Mohar","year":"2001"},{"key":"S0963548321000213_ref40","unstructured":"[40] Liu, C.-H. and Wood, D. R. (2019 c) Clustered variants of Haj\u00f3s\u2019 conjecture. arXiv:1908.05597."},{"key":"S0963548321000213_ref1","doi-asserted-by":"publisher","DOI":"10.1016\/S0095-8956(02)00006-0"},{"key":"S0963548321000213_ref31","doi-asserted-by":"publisher","DOI":"10.1016\/S0095-8956(03)00031-5"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548321000213","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,5]],"date-time":"2023-11-05T02:40:37Z","timestamp":1699152037000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548321000213\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,18]]},"references-count":55,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,1]]}},"alternative-id":["S0963548321000213"],"URL":"https:\/\/doi.org\/10.1017\/s0963548321000213","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,6,18]]},"assertion":[{"value":"\u00a9 The Author(s), 2021. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}}]}}