{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,3]],"date-time":"2025-12-03T18:02:51Z","timestamp":1764784971138,"version":"3.40.5"},"reference-count":29,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2022,9,30]],"date-time":"2022-09-30T00:00:00Z","timestamp":1664496000000},"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,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Strengthening Hadwiger\u2019s conjecture, Gerards and Seymour conjectured in 1995 that every graph with no odd <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000268_inline1.png\"\/><jats:tex-math>\n$K_t$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-minor is properly <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000268_inline2.png\"\/><jats:tex-math>\n$(t-1)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-colourable. This is known as the <jats:italic>Odd Hadwiger\u2019s conjecture<\/jats:italic>. We prove a relaxation of the above conjecture, namely we show that every graph with no odd <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000268_inline3.png\"\/><jats:tex-math>\n$K_t$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-minor admits a vertex <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000268_inline4.png\"\/><jats:tex-math>\n$(2t-2)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-colouring such that all monochromatic components have size at most <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000268_inline5.png\"\/><jats:tex-math>\n$\\lceil \\frac{1}{2}(t-2) \\rceil$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. The bound on the number of colours is optimal up to a factor of <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000268_inline6.png\"\/><jats:tex-math>\n$2$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, improves previous bounds for the same problem by Kawarabayashi (2008, <jats:italic>Combin. Probab. Comput.<\/jats:italic><jats:bold>17<\/jats:bold> 815\u2013821), Kang and Oum (2019, <jats:italic>Combin. Probab. Comput.<\/jats:italic><jats:bold>28<\/jats:bold> 740\u2013754), Liu and Wood (2021, arXiv preprint, arXiv:1905.09495), and strengthens a result by van den Heuvel and Wood (2018, <jats:italic>J. Lond. Math. Soc.<\/jats:italic><jats:bold>98<\/jats:bold> 129\u2013148), who showed that the above conclusion holds under the more restrictive assumption that the graph is <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000268_inline7.png\"\/><jats:tex-math>\n$K_t$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-minor-free. In addition, the bound on the component-size in our result is much smaller than those of previous results, in which the dependency on <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000268_inline8.png\"\/><jats:tex-math>\n$t$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> was given by a function arising from the graph minor structure theorem of Robertson and Seymour. Our short proof combines the method by van den Heuvel and Wood for <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000268_inline9.png\"\/><jats:tex-math>\n$K_t$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-minor-free graphs with some additional ideas, which make the extension to odd <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548322000268_inline10.png\"\/><jats:tex-math>\n$K_t$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-minor-free graphs possible.<\/jats:p>","DOI":"10.1017\/s0963548322000268","type":"journal-article","created":{"date-parts":[[2022,9,30]],"date-time":"2022-09-30T07:55:52Z","timestamp":1664524552000},"page":"326-333","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":2,"title":["Improved bound for improper colourings of graphs with no odd clique minor"],"prefix":"10.1017","volume":"32","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4234-6136","authenticated-orcid":false,"given":"Raphael","family":"Steiner","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2022,9,30]]},"reference":[{"doi-asserted-by":"publisher","key":"S0963548322000268_ref26","DOI":"10.1016\/j.jctb.2022.02.002"},{"unstructured":"[18] Norin, S. , Postle, L. and Song, Z.-X. (2019) Breaking the degeneracy barrier for coloring graphs with no $K_t$ minor. arXiv preprint, arXiv: 1910.09378.","key":"S0963548322000268_ref18"},{"key":"S0963548322000268_ref7","first-page":"133","article-title":"\u00dcber eine Klassifikation der Streckenkomplexe","volume":"88","author":"Hadwiger","year":"1943","journal-title":"Vierteljahrsschr Naturforsch. Ges. Z\u00fcr"},{"key":"S0963548322000268_ref6","first-page":"115","volume-title":"Graph Coloring Problems","author":"Jensen","year":"1995"},{"doi-asserted-by":"publisher","key":"S0963548322000268_ref13","DOI":"10.1016\/j.ejc.2007.02.010"},{"unstructured":"[3] Dvo\u0159\u00e1k, Z. and Norin, S. (2017) Islands in minor-closed classes. I. Bounded treewidth and separators. arXiv preprint, arXiv: 1710.02727.","key":"S0963548322000268_ref3"},{"doi-asserted-by":"publisher","key":"S0963548322000268_ref8","DOI":"10.1112\/jlms.12127"},{"doi-asserted-by":"publisher","key":"S0963548322000268_ref4","DOI":"10.1137\/141002177"},{"unstructured":"[23] Postle, L. (2020) Further progress towards the list and odd versions of Hadwiger\u2019s conjecture. arXiv preprint, arXiv: 2010.05999.","key":"S0963548322000268_ref23"},{"doi-asserted-by":"publisher","key":"S0963548322000268_ref5","DOI":"10.1016\/j.jctb.2008.03.006"},{"key":"S0963548322000268_ref20","article-title":"A new upper bound on the chromatic number of graphs with no odd \n\n\n\n$K_t$\n\n\n minor","author":"Norin","year":"2021","journal-title":"Combinatorica"},{"doi-asserted-by":"publisher","key":"S0963548322000268_ref27","DOI":"10.1017\/S0305004100061521"},{"doi-asserted-by":"publisher","key":"S0963548322000268_ref25","DOI":"10.1007\/978-3-319-32162-2_13"},{"doi-asserted-by":"publisher","key":"S0963548322000268_ref15","DOI":"10.1007\/BF02579141"},{"doi-asserted-by":"publisher","key":"S0963548322000268_ref14","DOI":"10.1007\/s00493-007-2213-9"},{"doi-asserted-by":"publisher","key":"S0963548322000268_ref1","DOI":"10.1016\/0095-8956(79)90062-5"},{"doi-asserted-by":"publisher","key":"S0963548322000268_ref28","DOI":"10.1016\/j.ejc.2010.05.015"},{"doi-asserted-by":"publisher","key":"S0963548322000268_ref24","DOI":"10.1007\/BF01202354"},{"doi-asserted-by":"publisher","key":"S0963548322000268_ref9","DOI":"10.1017\/S0963548318000548"},{"doi-asserted-by":"publisher","key":"S0963548322000268_ref12","DOI":"10.1016\/j.jctb.2006.11.002"},{"key":"S0963548322000268_ref19","first-page":"107","article-title":"Connectivity and choosability of graphs with no \n\n\n\n$K_t$\n\n\n minor","volume":"1","author":"Norin","year":"2020","journal-title":"J. Combin. Theory Ser. B"},{"doi-asserted-by":"publisher","key":"S0963548322000268_ref16","DOI":"10.1016\/j.jctb.2017.08.003"},{"unstructured":"[21] Postle, L. (2020) Further progress towards Hadwiger\u2019s conjecture. arXiv preprint, arXiv: 2006.11798.","key":"S0963548322000268_ref21"},{"doi-asserted-by":"publisher","key":"S0963548322000268_ref11","DOI":"10.1016\/j.jctb.2008.12.001"},{"unstructured":"[2] Delcourt, M. and Postle, L. (2021) Reducing linear Hadwiger\u2019s conjecture to coloring small graphs. arXiv preprint, arXiv: 2108.01633.","key":"S0963548322000268_ref2"},{"key":"S0963548322000268_ref29","first-page":"DS23","article-title":"Defective and clustered graph colouring","author":"Wood","year":"2018","journal-title":"Electron. J. Combin. Dyn. Surv."},{"doi-asserted-by":"publisher","key":"S0963548322000268_ref10","DOI":"10.1017\/S0963548308009462"},{"unstructured":"[17] Liu, C.-H. and Wood, D. R. (2021) Clustered coloring of graphs excluding a subgraph and a minor. arXiv preprint, arXiv: 1905.09495.","key":"S0963548322000268_ref17"},{"unstructured":"[22] Postle, L. (2020) An even better density increment theorem and its application to Hadwiger\u2019s conjecture. arXiv preprint, arXiv: 2006.14945.","key":"S0963548322000268_ref22"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548322000268","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,15]],"date-time":"2023-02-15T08:42:27Z","timestamp":1676450547000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548322000268\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,9,30]]},"references-count":29,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,3]]}},"alternative-id":["S0963548322000268"],"URL":"https:\/\/doi.org\/10.1017\/s0963548322000268","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"type":"print","value":"0963-5483"},{"type":"electronic","value":"1469-2163"}],"subject":[],"published":{"date-parts":[[2022,9,30]]},"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"}]}}