{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,13]],"date-time":"2025-05-13T21:58:53Z","timestamp":1747173533631,"version":"3.40.5"},"reference-count":27,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2023,11,10]],"date-time":"2023-11-10T00:00:00Z","timestamp":1699574400000},"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,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A collection of graphs is <jats:italic>nearly disjoint<\/jats:italic> if every pair of them intersects in at most one vertex. We prove that if <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548323000299_inline1.png\"\/><jats:tex-math>\n$G_1, \\dots, G_m$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> are nearly disjoint graphs of maximum degree at most <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548323000299_inline2.png\"\/><jats:tex-math>\n$D$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, then the following holds. For every fixed <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548323000299_inline3.png\"\/><jats:tex-math>\n$C$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, if each vertex <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548323000299_inline4.png\"\/><jats:tex-math>\n$v \\in \\bigcup _{i=1}^m V(G_i)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> is contained in at most <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548323000299_inline5.png\"\/><jats:tex-math>\n$C$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> of the graphs <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548323000299_inline6.png\"\/><jats:tex-math>\n$G_1, \\dots, G_m$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, then the (list) chromatic number of <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548323000299_inline7.png\"\/><jats:tex-math>\n$\\bigcup _{i=1}^m G_i$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> is at most <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548323000299_inline8.png\"\/><jats:tex-math>\n$D + o(D)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. This result confirms a special case of a conjecture of Vu and generalizes Kahn\u2019s bound on the list chromatic index of linear uniform hypergraphs of bounded maximum degree. In fact, this result holds for the correspondence (or DP) chromatic number and thus implies a recent result of Molloy and Postle, and we derive this result from a more general list colouring result in the setting of \u2018colour degrees\u2019 that also implies a result of Reed and Sudakov.<\/jats:p>","DOI":"10.1017\/s0963548323000299","type":"journal-article","created":{"date-parts":[[2023,11,10]],"date-time":"2023-11-10T07:16:26Z","timestamp":1699600586000},"page":"179-195","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":0,"title":["A special case of Vu\u2019s conjecture: colouring nearly disjoint graphs of bounded maximum degree"],"prefix":"10.1017","volume":"33","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4040-1648","authenticated-orcid":false,"given":"Tom","family":"Kelly","sequence":"first","affiliation":[]},{"given":"Daniela","family":"K\u00fchn","sequence":"additional","affiliation":[]},{"given":"Deryk","family":"Osthus","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2023,11,10]]},"reference":[{"key":"S0963548323000299_ref16","doi-asserted-by":"publisher","DOI":"10.4171\/8ecm\/11"},{"key":"S0963548323000299_ref14","doi-asserted-by":"publisher","DOI":"10.1006\/jcta.1996.0001"},{"key":"S0963548323000299_ref15","unstructured":"[15] Kang, D. Y. , Kelly, T. , K\u00fchn, D. , Methuku, A. and Osthus, D. (2021) Solution to a problem of Erd\u0151s on the chromatic index of hypergraphs with bounded codegree, arXiv: 2110.06181."},{"key":"S0963548323000299_ref6","doi-asserted-by":"publisher","DOI":"10.4153\/S0008439521001004"},{"key":"S0963548323000299_ref13","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(92)90096-D"},{"key":"S0963548323000299_ref20","doi-asserted-by":"publisher","DOI":"10.1002\/1098-2418(200010\/12)17:3\/4<376::AID-RSA10>3.0.CO;2-0"},{"key":"S0963548323000299_ref25","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.2002.2110"},{"key":"S0963548323000299_ref22","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(89)90074-5"},{"key":"S0963548323000299_ref1","volume-title":"Algorithms and Techniques","volume":"176","author":"Alon","year":"2020"},{"key":"S0963548323000299_ref11","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548301004758"},{"key":"S0963548323000299_ref17","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2023.198.2.2"},{"key":"S0963548323000299_ref5","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548317000244"},{"key":"S0963548323000299_ref12","article-title":"An improved procedure for colouring graphs of bounded local density","author":"Hurley","year":"2022","journal-title":"Adv. Comb."},{"key":"S0963548323000299_ref19","first-page":"1","article-title":"Asymptotically good edge correspondence colourings","author":"Molloy","year":"2022","journal-title":"J. Graph Theory"},{"key":"S0963548323000299_ref23","unstructured":"[23] Postle, L. personal communication."},{"key":"S0963548323000299_ref8","first-page":"153","volume-title":"Graph Theory and Related Topics (Proc. Conf., Univ. Waterloo, Waterloo, Ont., 1977)","author":"Erd\u0151s","year":"1979"},{"key":"S0963548323000299_ref4","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.10054"},{"key":"S0963548323000299_ref10","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2022.01.004"},{"key":"S0963548323000299_ref9","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579174"},{"key":"S0963548323000299_ref24","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0118(199906)31:2<149::AID-JGT8>3.0.CO;2-#"},{"key":"S0963548323000299_ref21","volume-title":"Algorithms and Combinatorics","volume":"23","author":"Molloy","year":"2002"},{"key":"S0963548323000299_ref26","doi-asserted-by":"publisher","DOI":"10.1007\/BF02699376"},{"key":"S0963548323000299_ref3","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548322000104"},{"key":"S0963548323000299_ref7","first-page":"609","volume-title":"Infinite and Finite Sets (Colloq., Keszthely, 1973; dedicated to P. Erd\u0151s on his 60th birthday), Vol. II","volume":"10","author":"Erd\u0151s","year":"1975"},{"key":"S0963548323000299_ref18","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.21051"},{"key":"S0963548323000299_ref2","doi-asserted-by":"crossref","unstructured":"[2] Anderson, J. , Bernshteyn, A. and Dhawan, A. (2021) Coloring graphs with forbidden bipartite subgraphs, arXiv:2107.05595.","DOI":"10.1017\/S0963548322000104"},{"key":"S0963548323000299_ref27","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548301004898"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548323000299","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,5]],"date-time":"2024-02-05T11:23:01Z","timestamp":1707132181000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548323000299\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,11,10]]},"references-count":27,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,3]]}},"alternative-id":["S0963548323000299"],"URL":"https:\/\/doi.org\/10.1017\/s0963548323000299","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"type":"print","value":"0963-5483"},{"type":"electronic","value":"1469-2163"}],"subject":[],"published":{"date-parts":[[2023,11,10]]},"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"}]}}