{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,27]],"date-time":"2026-06-27T13:28:20Z","timestamp":1782566900481,"version":"3.54.5"},"reference-count":25,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2022,6,8]],"date-time":"2022-06-08T00:00:00Z","timestamp":1654646400000},"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":[[2023,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A conjecture of Alon, Krivelevich and Sudakov states that, for any graph <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000104_inline1.png\"\/><jats:tex-math>\n$F$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, there is a constant <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000104_inline2.png\"\/><jats:tex-math>\n$c_F \\gt 0$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> such that if <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000104_inline3.png\"\/><jats:tex-math>\n$G$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> is an <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000104_inline4.png\"\/><jats:tex-math>\n$F$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-free graph of maximum degree <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000104_inline5.png\"\/><jats:tex-math>\n$\\Delta$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, then <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000104_inline6.png\"\/><jats:tex-math>\n$\\chi\\!(G) \\leqslant c_F \\Delta\/ \\log\\!\\Delta$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. Alon, Krivelevich and Sudakov verified this conjecture for a class of graphs <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000104_inline7.png\"\/><jats:tex-math>\n$F$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> that includes all bipartite graphs. Moreover, it follows from recent work by Davies, Kang, Pirot and Sereni that if <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000104_inline8.png\"\/><jats:tex-math>\n$G$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> is <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000104_inline9.png\"\/><jats:tex-math>\n$K_{t,t}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-free, then <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000104_inline10.png\"\/><jats:tex-math>\n$\\chi\\!(G) \\leqslant (t + o(1)) \\Delta\/ \\log\\!\\Delta$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> as <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000104_inline11.png\"\/><jats:tex-math>\n$\\Delta \\to \\infty$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. We improve this bound to <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000104_inline12.png\"\/><jats:tex-math>\n$(1+o(1)) \\Delta\/\\log\\!\\Delta$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, making the constant factor independent of <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000104_inline13.png\"\/><jats:tex-math>\n$t$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. We further extend our result to the DP-colouring setting (also known as correspondence colouring), introduced by Dvo\u0159\u00e1k and Postle.<\/jats:p>","DOI":"10.1017\/s0963548322000104","type":"journal-article","created":{"date-parts":[[2022,6,8]],"date-time":"2022-06-08T06:41:37Z","timestamp":1654670497000},"page":"45-67","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":7,"title":["Colouring graphs with forbidden bipartite subgraphs"],"prefix":"10.1017","volume":"32","author":[{"given":"James","family":"Anderson","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8070-3408","authenticated-orcid":false,"given":"Anton","family":"Bernshteyn","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Abhishek","family":"Dhawan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"56","published-online":{"date-parts":[[2022,6,8]]},"reference":[{"key":"S0963548322000104_ref17","unstructured":"[17] Kang, D. , Kelly, T. , K\u00fchn, D. , Methuku, A. and Osthus, D. (2021) Graph and hypergraph colouring via nibble methods: A survey. Available at: https:\/\/arxiv.org\/pdf\/2106.13733 (preprint)."},{"key":"S0963548322000104_ref5","doi-asserted-by":"crossref","unstructured":"[5] Anderson, J. , Bernshteyn, A. and Dhawan, A. (2022) Coloring graphs with forbidden almost bipartite subgraphs. Available at: https:\/\/arxiv.org\/abs\/2203.07222 (preprint).","DOI":"10.1017\/S0963548322000104"},{"key":"S0963548322000104_ref15","unstructured":"[15] Johansson, A. (1996) Asymptotic Choice Number for Triangle Free Graphs. DIMACS, Technical Report 91\u201395."},{"key":"S0963548322000104_ref16","unstructured":"[16] Johansson, A. (1996) The choice number of sparse graphs. Available at: https:\/\/www.cs.cmu.edu\/\u223canupamg\/down\/jo- hansson-choice-number-of-sparse-graphs-coloring-kr-free.pdf (preprint)."},{"key":"S0963548322000104_ref8","article-title":"Colouring Graphs with Sparse Neighbourhoods","author":"Bonamy","year":"2018","journal-title":"Bounds Appl"},{"key":"S0963548322000104_ref4","doi-asserted-by":"publisher","DOI":"10.1016\/j.endm.2008.01.024"},{"key":"S0963548322000104_ref14","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579157"},{"key":"S0963548322000104_ref22","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04016-0"},{"key":"S0963548322000104_ref24","doi-asserted-by":"publisher","DOI":"10.1214\/16-AOP1094"},{"key":"S0963548322000104_ref18","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548300001528"},{"key":"S0963548322000104_ref2","unstructured":"[2] Alon, N. and Assadi, S. (2020) Palette sparsification beyond $(\\Delta +1)$ vertex coloring . Available at: https:\/\/arxiv.org\/abs\/2006.10456 (preprint)."},{"key":"S0963548322000104_ref3","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1006\/jctb.1999.1910","article-title":"Coloring graphs with sparse neighborhoods","volume":"77","author":"Alon","year":"1999","journal-title":"J. Combin. Theory, Ser. B"},{"key":"S0963548322000104_ref11","unstructured":"[11] Davies, E. , Kang, R. , Pirot, F. and Sereni, J.-S. (2020) Graph structure via local occupancy. Available at: https:\/\/arxiv.org\/abs\/2003.14361 (preprint)."},{"key":"S0963548322000104_ref9","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548317000244"},{"key":"S0963548322000104_ref7","doi-asserted-by":"crossref","first-page":"433","DOI":"10.2307\/2043545","article-title":"The independence ratio of regular graphs","volume":"83","author":"Bollob\u00e1s","year":"1981","journal-title":"Proc. Am. Math. Soc."},{"key":"S0963548322000104_ref21","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2018.06.007"},{"key":"S0963548322000104_ref23","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2014.12.018"},{"key":"S0963548322000104_ref19","doi-asserted-by":"publisher","DOI":"10.4064\/cm-3-1-50-57"},{"key":"S0963548322000104_ref20","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579283"},{"key":"S0963548322000104_ref25","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.76.031131"},{"key":"S0963548322000104_ref12","doi-asserted-by":"crossref","first-page":"38","DOI":"10.1016\/j.jctb.2017.09.001","article-title":"Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8","volume":"129","author":"Dv\u01d2r\u00e1k","year":"2018","journal-title":"J. Combin. Theory Ser. B"},{"key":"S0963548322000104_ref1","first-page":"793","article-title":"Algorithmic barriers from phase transitions","author":"Achlioptas","year":"2008","journal-title":"IEEE Symp. Found. Comput. Sci. (FOCS)"},{"key":"S0963548322000104_ref10","unstructured":"[10] Cambie, S. and Kang, R. (2020) Independent transversals in bipartite correspondence-covers. Available at: https:\/\/arxiv.org\/abs\/2009.05428 (preprint)."},{"key":"S0963548322000104_ref6","doi-asserted-by":"crossref","first-page":"653","DOI":"10.1002\/rsa.20811","article-title":"The Johansson-Molloy theorem for DP-coloring","volume":"54","author":"Bernshteyn","year":"2019","journal-title":"Rand. Struct. Algor."},{"key":"S0963548322000104_ref13","doi-asserted-by":"crossref","first-page":"61","DOI":"10.4064\/cm-6-1-61-65","article-title":"On a combinatorial problem","volume":"6","author":"Hylt\u00e9n-Cavallius","year":"1958","journal-title":"Colloq. Math."}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548322000104","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,20]],"date-time":"2022-12-20T05:08:26Z","timestamp":1671512906000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548322000104\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,8]]},"references-count":25,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,1]]}},"alternative-id":["S0963548322000104"],"URL":"https:\/\/doi.org\/10.1017\/s0963548322000104","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,6,8]]},"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"}},{"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"}]}}