{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,13]],"date-time":"2025-05-13T21:58:54Z","timestamp":1747173534042,"version":"3.40.5"},"reference-count":39,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2023,11,3]],"date-time":"2023-11-03T00:00:00Z","timestamp":1698969600000},"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":"Abstract<\/jats:title>Given a graph \n$H$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, let us denote by \n$f_\\chi (H)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> and \n$f_\\ell (H)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, respectively, the maximum chromatic number and the maximum list chromatic number of \n$H$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-minor-free graphs. Hadwiger\u2019s famous colouring conjecture from 1943 states that \n$f_\\chi (K_t)=t-1$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> for every \n$t \\ge 2$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. A closely related problem that has received significant attention in the past concerns \n$f_\\ell (K_t)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, for which it is known that \n$2t-o(t) \\le f_\\ell (K_t) \\le O(t (\\!\\log \\log t)^6)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. Thus, \n$f_\\ell (K_t)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> is bounded away from the conjectured value \n$t-1$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> for \n$f_\\chi (K_t)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> by at least a constant factor. The so-called \n$H$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-Hadwiger\u2019s conjecture, proposed by Seymour, asks to prove that \n$f_\\chi (H)={\\textrm{v}}(H)-1$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> for a given graph \n$H$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> (which would be implied by Hadwiger\u2019s conjecture).<\/jats:p>In this paper, we prove several new lower bounds on \n$f_\\ell (H)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, thus exploring the limits of a list colouring extension of \n$H$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-Hadwiger\u2019s conjecture. Our main results are:<\/jats:p>For every \n$\\varepsilon \\gt 0$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> and all sufficiently large graphs \n$H$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> we have \n$f_\\ell (H)\\ge (1-\\varepsilon )({\\textrm{v}}(H)+\\kappa (H))$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, where \n$\\kappa (H)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> denotes the vertex-connectivity of \n$H$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>.<\/jats:p><\/jats:list-item>For every \n$\\varepsilon \\gt 0$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> there exists \n$C=C(\\varepsilon )\\gt 0$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> such that asymptotically almost every \n$n$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-vertex graph \n$H$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> with \n$\\left \\lceil C n\\log n\\right \\rceil$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> edges satisfies \n$f_\\ell (H)\\ge (2-\\varepsilon )n$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>.<\/jats:p><\/jats:list-item><\/jats:list><\/jats:p>The first result generalizes recent results on complete and complete bipartite graphs and shows that the list chromatic number of \n$H$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-minor-free graphs is separated from the desired value of \n$({\\textrm{v}}(H)-1)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> by a constant factor for all large graphs \n$H$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> of linear connectivity. The second result tells us that for almost all graphs \n$H$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> with superlogarithmic average degree \n$f_\\ell (H)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> is separated from \n$({\\textrm{v}}(H)-1)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> by a constant factor arbitrarily close to \n$2$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. Conceptually these results indicate that the graphs \n$H$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> for which \n$f_\\ell (H)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> is close to the conjectured value \n$({\\textrm{v}}(H)-1)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> for \n$f_\\chi (H)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> are typically rather sparse.<\/jats:p>","DOI":"10.1017\/s0963548323000354","type":"journal-article","created":{"date-parts":[[2023,11,3]],"date-time":"2023-11-03T06:01:07Z","timestamp":1698991267000},"page":"129-142","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":0,"title":["On the choosability of -minor-free graphs"],"prefix":"10.1017","volume":"33","author":[{"given":"Olivier","family":"Fischer","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4234-6136","authenticated-orcid":false,"given":"Raphael","family":"Steiner","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2023,11,3]]},"reference":[{"key":"S0963548323000354_ref20","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2023.109020"},{"key":"S0963548323000354_ref4","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1016\/0012-365X(93)90557-A","article-title":"Research problem 172","volume":"121","author":"Borowiecki","year":"1993","journal-title":"Discrete Math."},{"key":"S0963548323000354_ref5","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2010.09.001"},{"key":"S0963548323000354_ref34","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1994.1062"},{"key":"S0963548323000354_ref13","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579141"},{"key":"S0963548323000354_ref33","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100061521"},{"key":"S0963548323000354_ref2","first-page":"491","article-title":"Every planar map is four colorable. Part II. Reducibility","volume":"21","author":"Appel","year":"1977","journal-title":"Ill. J. Math."},{"key":"S0963548323000354_ref8","first-page":"133","article-title":"\u00dcber eine Klassifikation der Streckenkomplexe","volume":"88","author":"Hadwiger","year":"1943","journal-title":"Vierteljahrsschrift der Naturforschenden Gesellschaft in Z\u00fcrich"},{"key":"S0963548323000354_ref16","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2010.03.026"},{"key":"S0963548323000354_ref36","doi-asserted-by":"publisher","DOI":"10.1007\/BF01360256"},{"key":"S0963548323000354_ref38","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511721328.012"},{"key":"S0963548323000354_ref7","first-page":"125","volume-title":"Proc. West Coast Conference on Combinatorics, Graph Theory and Computing, Arcata","volume":"26","author":"Erd\u0151s","year":"1979"},{"key":"S0963548323000354_ref29","unstructured":"[28] Seymour, P. (2017) BIRS Workshop: Geometric and Structural Graph Theory\u2013Open Problems. https:\/\/drive.google.com\/file\/d\/1SZCJ-bc8qPXKlkfVFyAocX5bU8W5JYbv\/view"},{"key":"S0963548323000354_ref11","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2008.08.015"},{"key":"S0963548323000354_ref15","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.21744"},{"key":"S0963548323000354_ref32","doi-asserted-by":"publisher","DOI":"10.37236\/10994"},{"key":"S0963548323000354_ref1","first-page":"429","article-title":"Every planar map is four colorable. Part I. Discharging","volume":"21","author":"Appel","year":"1977","journal-title":"Ill. J. Math."},{"key":"S0963548323000354_ref14","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.20485"},{"key":"S0963548323000354_ref35","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(93)90579-I"},{"key":"S0963548323000354_ref37","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2010.05.015"},{"key":"S0963548323000354_ref17","doi-asserted-by":"publisher","DOI":"10.1007\/BF02993903"},{"key":"S0963548323000354_ref21","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2021.02.001"},{"key":"S0963548323000354_ref26","unstructured":"[25] Postle, L. (2020) Further progress towards the list and odd versions of Hadwiger\u2019s conjecture. arXiv preprint, arXiv: 2010.05999."},{"key":"S0963548323000354_ref25","unstructured":"[24] Postle, L. (2020) An even better density increment theorem and its application to Hadwiger\u2019s conjecture. arXiv preprint, arXiv: 2006.14945."},{"key":"S0963548323000354_ref18","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(03)00051-7"},{"key":"S0963548323000354_ref12","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2006.11.002"},{"key":"S0963548323000354_ref28","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-32162-2_13"},{"key":"S0963548323000354_ref3","doi-asserted-by":"publisher","DOI":"10.37236\/719"},{"key":"S0963548323000354_ref24","unstructured":"[23] Postle, L. (2020) Further progress towards Hadwiger\u2019s conjecture. arXiv preprint, arXiv: 2006.11798."},{"key":"S0963548323000354_ref10","doi-asserted-by":"publisher","DOI":"10.1007\/PL00007245"},{"key":"S0963548323000354_ref19","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781316106853.008"},{"key":"S0963548323000354_ref6","unstructured":"[6] Delcourt, M. and Postle, L. (2021) Reducing Linear Hadwiger\u2019s Conjecture to Coloring Small Graphs. arXiv preprint, arXiv: 2108.01633."},{"key":"S0963548323000354_ref23","unstructured":"[22] Norin, S. and Turcotte, J. (2023) Limits of degeneracy for colouring graphs with forbidden minors. arXiv preprint, arXiv:2304.13715."},{"key":"S0963548323000354_ref9","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2018.02.001"},{"key":"S0963548323000354_ref30","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(98)00158-7"},{"key":"S0963548323000354_ref27","doi-asserted-by":"publisher","DOI":"10.1007\/BF01202354"},{"key":"S0963548323000354_ref31","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548322000116"},{"key":"S0963548323000354_ref39","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.10153"},{"key":"S0963548323000354_ref40","unstructured":"[39] Open Problem Garden. List Hadwiger Conjecture. http:\/\/www.openproblemgarden.org\/op\/list_hadwiger_conjecture"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548323000354","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,5]],"date-time":"2024-02-05T11:23:04Z","timestamp":1707132184000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548323000354\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,11,3]]},"references-count":39,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,3]]}},"alternative-id":["S0963548323000354"],"URL":"https:\/\/doi.org\/10.1017\/s0963548323000354","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"type":"print","value":"0963-5483"},{"type":"electronic","value":"1469-2163"}],"subject":[],"published":{"date-parts":[[2023,11,3]]},"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"}]}}