{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T14:46:30Z","timestamp":1770993990491,"version":"3.50.1"},"reference-count":43,"publisher":"Cambridge University Press (CUP)","issue":"5","license":[{"start":{"date-parts":[[2019,4,12]],"date-time":"2019-04-12T00:00:00Z","timestamp":1555027200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2019,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>An (improper) graph colouring has<jats:italic>defect d<\/jats:italic>if each monochromatic subgraph has maximum degree at most<jats:italic>d<\/jats:italic>, and has<jats:italic>clustering c<\/jats:italic>if each monochromatic component has at most<jats:italic>c<\/jats:italic>vertices. This paper studies defective and clustered list-colourings for graphs with given maximum average degree. We prove that every graph with maximum average degree less than (2<jats:italic>d<\/jats:italic>+2)\/(<jats:italic>d<\/jats:italic>+2)<jats:italic>k<\/jats:italic>is<jats:italic>k<\/jats:italic>-choosable with defect<jats:italic>d<\/jats:italic>. This improves upon a similar result by Havet and Sereni (<jats:italic>J. Graph Theory<\/jats:italic>, 2006). For clustered choosability of graphs with maximum average degree<jats:italic>m<\/jats:italic>, no (1-<jats:italic>\u025b<\/jats:italic>)<jats:italic>m<\/jats:italic>bound on the number of colours was previously known. The above result with<jats:italic>d<\/jats:italic>=1 solves this problem. It implies that every graph with maximum average degree<jats:italic>m<\/jats:italic>is<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548319000063_inline1\"\/><jats:tex-math>$\\lfloor{\\frac{3}{4}m+1}\\rfloor$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-choosable with clustering 2. This extends a result of Kopreski and Yu (<jats:italic>Discrete Math.<\/jats:italic>, 2017) to the setting of choosability. We then prove two results about clustered choosability that explore the trade-off between the number of colours and the clustering. In particular, we prove that every graph with maximum average degree<jats:italic>m<\/jats:italic>is<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548319000063_inline2\"\/><jats:tex-math>$\\lfloor{\\frac{7}{10}m+1}\\rfloor$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-choosable with clustering 9, and is<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548319000063_inline3\"\/><jats:tex-math>$\\lfloor{\\frac{2}{3}m+1}\\rfloor$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-choosable with clustering<jats:italic>O<\/jats:italic>(<jats:italic>m<\/jats:italic>). As an example, the later result implies that every biplanar graph is 8-choosable with bounded clustering. This is the best known result for the clustered version of the earth\u2013moon problem. The results extend to the setting where we only consider the maximum average degree of subgraphs with at least some number of vertices. Several applications are presented.<\/jats:p>","DOI":"10.1017\/s0963548319000063","type":"journal-article","created":{"date-parts":[[2019,4,12]],"date-time":"2019-04-12T07:06:59Z","timestamp":1555052819000},"page":"791-810","source":"Crossref","is-referenced-by-count":10,"title":["Defective and clustered choosability of sparse graphs"],"prefix":"10.1017","volume":"28","author":[{"given":"Kevin","family":"Hendrey","sequence":"first","affiliation":[]},{"given":"David R.","family":"Wood","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2019,4,12]]},"reference":[{"key":"S0963548319000063_ref36","article-title":"Partitioning H-minor free graphs into three subgraphs with no large components","author":"Liu","year":"2017","journal-title":"J. Combin. Theory Ser. B."},{"key":"S0963548319000063_ref22","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2017.09.001"},{"key":"S0963548319000063_ref16","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2009.11.013"},{"key":"S0963548319000063_ref18","unstructured":"[18] Dujmovi\u0107, V. and Outioua, D. (2018) A note on defect-1 choosability of graphs on surfaces. arXiv:1806.06149"},{"key":"S0963548319000063_ref27","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.20155"},{"key":"S0963548319000063_ref38","doi-asserted-by":"publisher","DOI":"10.1007\/PL00007219"},{"key":"S0963548319000063_ref28","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548301004758"},{"key":"S0963548319000063_ref11","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2013.07.014"},{"key":"S0963548319000063_ref3","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190110408"},{"key":"S0963548319000063_ref33","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2014.05.003"},{"key":"S0963548319000063_ref2","doi-asserted-by":"publisher","DOI":"10.1016\/S0095-8956(02)00006-0"},{"key":"S0963548319000063_ref30","doi-asserted-by":"publisher","DOI":"10.1112\/jlms.12127"},{"key":"S0963548319000063_ref6","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.20467"},{"key":"S0963548319000063_ref20","first-page":"339","article-title":"On linear layouts of graphs","volume":"6","author":"Dujmovi\u0107","year":"2004","journal-title":"Discrete Math. Theor. Comput. Sci."},{"key":"S0963548319000063_ref15","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0118(199703)24:3<205::AID-JGT2>3.0.CO;2-T"},{"key":"S0963548319000063_ref43","doi-asserted-by":"publisher","DOI":"10.7151\/dmgt.1557"},{"key":"S0963548319000063_ref32","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(99)00278-2"},{"key":"S0963548319000063_ref14","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190100207"},{"key":"S0963548319000063_ref5","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.20516"},{"key":"S0963548319000063_ref12","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.20282"},{"key":"S0963548319000063_ref1","doi-asserted-by":"publisher","DOI":"10.26493\/1855-3974.175.b78"},{"key":"S0963548319000063_ref4","first-page":"16","article-title":"Almost proper 2-colorings of vertices of sparse graphs","volume":"16","author":"Borodin","year":"2009","journal-title":"Diskretn. Anal. Issled. Oper."},{"key":"S0963548319000063_ref24","doi-asserted-by":"publisher","DOI":"10.1137\/141002177"},{"key":"S0963548319000063_ref7","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2011.06.021"},{"key":"S0963548319000063_ref8","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2011.11.031"},{"key":"S0963548319000063_ref10","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2013.10.002"},{"key":"S0963548319000063_ref13","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22418"},{"key":"S0963548319000063_ref17","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.21731"},{"key":"S0963548319000063_ref19","doi-asserted-by":"publisher","DOI":"10.4086\/cjtcs.2016.001"},{"key":"S0963548319000063_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":"S0963548319000063_ref40","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-018-3733-1"},{"key":"S0963548319000063_ref23","first-page":"79","article-title":"Defective list colorings of planar graphs","volume":"25","author":"Eaton","year":"1999","journal-title":"Bull. Inst. Combin. Appl"},{"key":"S0963548319000063_ref25","doi-asserted-by":"publisher","DOI":"10.1137\/140957883"},{"key":"S0963548319000063_ref26","doi-asserted-by":"publisher","DOI":"10.1007\/s00373-008-0833-5"},{"key":"S0963548319000063_ref29","doi-asserted-by":"publisher","DOI":"10.1016\/S0095-8956(03)00031-5"},{"key":"S0963548319000063_ref31","doi-asserted-by":"publisher","DOI":"10.1080\/0025570X.1993.11996124"},{"key":"S0963548319000063_ref34","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.21886"},{"key":"S0963548319000063_ref9","first-page":"1004","article-title":"Vertex decompositions of sparse graphs into an independent set and a subgraph of maximum degree at most 1","volume":"52","author":"Borodin","year":"2011","journal-title":"Sibirsk. Mat. Zh."},{"key":"S0963548319000063_ref35","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2017.06.014"},{"key":"S0963548319000063_ref37","first-page":"237","article-title":"On decomposition of graphs","volume":"1","author":"Lov\u00e1sz","year":"1966","journal-title":"Studia Sci. Math. Hungar."},{"key":"S0963548319000063_ref39","unstructured":"[39] Norin, S. , Scott, A. , Seymour, P. , and Wood, D. R. (2017) Clustered colouring in minor-closed classes. ( S. Norin , A. Scott , P. Seymour and Wood, D. R. ), Combinatorica, accepted in 2019. arXiv:1708.02370"},{"key":"S0963548319000063_ref41","unstructured":"[41] Ringel, G. (1959) F\u00e4rbungsprobleme auf Fl\u00e4chen und Graphen, Vol. 2 of Mathematische Monographien, VEB, Deutscher Verlag der Wissenschaften."},{"key":"S0963548319000063_ref42","doi-asserted-by":"crossref","unstructured":"[42] Wood, D. R. (2018) Defective and clustered graph colouring. Electron. J. Combin. #DS23.","DOI":"10.37236\/7406"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548319000063","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,6]],"date-time":"2020-12-06T04:30:06Z","timestamp":1607229006000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548319000063\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,4,12]]},"references-count":43,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2019,9]]}},"alternative-id":["S0963548319000063"],"URL":"https:\/\/doi.org\/10.1017\/s0963548319000063","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,4,12]]}}}