{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T05:27:08Z","timestamp":1767245228945},"reference-count":31,"publisher":"Cambridge University Press (CUP)","issue":"5","license":[{"start":{"date-parts":[[2019,2,4]],"date-time":"2019-02-04T00:00:00Z","timestamp":1549238400000},"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>As a strengthening of Hadwiger\u2019s conjecture, Gerards and Seymour conjectured that every graph with no odd<jats:italic>K<jats:sub>t<\/jats:sub><\/jats:italic>minor is (<jats:italic>t<\/jats:italic>\u2212 1)-colourable. We prove two weaker variants of this conjecture. Firstly, we show that for each<jats:italic>t<\/jats:italic>\u2a7e 2, every graph with no odd<jats:italic>K<jats:sub>t<\/jats:sub><\/jats:italic>minor has a partition of its vertex set into 6<jats:italic>t<\/jats:italic>\u2212 9 sets<jats:italic>V<\/jats:italic><jats:sub>1<\/jats:sub>, \u2026,<jats:italic>V<\/jats:italic><jats:sub>6<\/jats:sub><jats:italic><jats:sub>t<\/jats:sub><\/jats:italic><jats:sub>\u22129<\/jats:sub>such that each<jats:italic>V<jats:sub>i<\/jats:sub><\/jats:italic>induces a subgraph of bounded maximum degree. Secondly, we prove that for each<jats:italic>t<\/jats:italic>\u2a7e 2, every graph with no odd Kt minor has a partition of its vertex set into 10<jats:italic>t<\/jats:italic>\u221213 sets<jats:italic>V<\/jats:italic><jats:sub>1<\/jats:sub>,\u2026,<jats:italic>V<\/jats:italic><jats:sub>10<\/jats:sub><jats:italic><jats:sub>t<\/jats:sub><\/jats:italic><jats:sub>\u221213<\/jats:sub>such that each<jats:italic>V<jats:sub>i<\/jats:sub><\/jats:italic>induces a subgraph with components of bounded size. The second theorem improves a result of Kawarabayashi (2008), which states that the vertex set can be partitioned into 496<jats:italic>t<\/jats:italic>such sets.<\/jats:p>","DOI":"10.1017\/s0963548318000548","type":"journal-article","created":{"date-parts":[[2019,2,4]],"date-time":"2019-02-04T07:45:20Z","timestamp":1549266320000},"page":"740-754","source":"Crossref","is-referenced-by-count":9,"title":["Improper colouring of graphs with no odd clique minor"],"prefix":"10.1017","volume":"28","author":[{"given":"Dong Yeap","family":"Kang","sequence":"first","affiliation":[]},{"given":"Sang-Il","family":"Oum","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2019,2,4]]},"reference":[{"key":"S0963548318000548_ref4","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-14279-6"},{"key":"S0963548318000548_ref3","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0118(199703)24:3<205::AID-JGT2>3.0.CO;2-T"},{"key":"S0963548318000548_ref20","first-page":"37","article-title":"The minimum Hadwiger number for graphs with a given mean degree of vertices","volume":"38","author":"Kostochka","year":"1982","journal-title":"Metody Diskret. Analiz."},{"key":"S0963548318000548_ref16","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.21680"},{"key":"S0963548318000548_ref6","doi-asserted-by":"publisher","DOI":"10.1137\/141002177"},{"key":"S0963548318000548_ref15","volume-title":"Graph Coloring Problems","author":"Jensen","year":"1995"},{"key":"S0963548318000548_ref30","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2010.05.015"},{"key":"S0963548318000548_ref19","doi-asserted-by":"publisher","DOI":"10.1017\/S096354830000184X"},{"key":"S0963548318000548_ref28","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100061521"},{"key":"S0963548318000548_ref22","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2017.08.003"},{"key":"S0963548318000548_ref7","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548314000170"},{"key":"S0963548318000548_ref2","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(79)90062-5"},{"key":"S0963548318000548_ref1","doi-asserted-by":"publisher","DOI":"10.1006\/eujc.1997.0188"},{"key":"S0963548318000548_ref12","first-page":"143","article-title":"(1953\u20131954) On the notion of balance of a signed graph","volume":"2","author":"Harary","journal-title":"Michigan Math. J."},{"key":"S0963548318000548_ref8","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2008.03.006"},{"key":"S0963548318000548_ref10","unstructured":"[10] Guenin, B. (2005) Odd-K5-free graphs are 4-colourable. In Oberwolfach Report no. 3\/2005, pp. 176\u2013178. https:\/\/www.mfo.de\/document\/0503\/OWR_2005_03.pdf"},{"key":"S0963548318000548_ref9","unstructured":"[9] Geelen, J. and Huynh, T. (2004) Colouring graphs with no odd-Kn minor. Manuscript. http:\/\/www.math.uwaterloo.ca\/~jfgeelen\/Publications\/colour.pdf"},{"key":"S0963548318000548_ref29","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.2000.2013"},{"key":"S0963548318000548_ref23","first-page":"236","article-title":"Colourings with bounded monochromatic components in graphs of given circumference","volume":"69","author":"Mohar","year":"2017","journal-title":"Australas. J. Combin."},{"key":"S0963548318000548_ref31","doi-asserted-by":"crossref","DOI":"10.37236\/7406","article-title":"Defective and clustered graph colouring","author":"Wood","year":"2018","journal-title":"Electron. J. Combin."},{"key":"S0963548318000548_ref27","volume-title":"Open Problems in Mathematics","author":"Seymour","year":"2016"},{"key":"S0963548318000548_ref26","doi-asserted-by":"publisher","DOI":"10.1007\/BF01202354"},{"key":"S0963548318000548_ref14","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2017.04.010"},{"key":"S0963548318000548_ref5","unstructured":"[5] Dvo\u0159\u00e1k, Z. and Norin, S. (2017) Islands in minor-closed classes, I: Bounded treewidth and separators. arXiv:1710.02727"},{"key":"S0963548318000548_ref17","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548308009462"},{"key":"S0963548318000548_ref18","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2006.11.002"},{"key":"S0963548318000548_ref24","unstructured":"[24] Norin, S. , Scott, A. , Seymour, P. and Wood, D. R. (2017) Clustered colouring in minor-closed classes. arXiv:1708.02370"},{"key":"S0963548318000548_ref21","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579141"},{"key":"S0963548318000548_ref25","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-018-3733-1"},{"key":"S0963548318000548_ref13","doi-asserted-by":"publisher","DOI":"10.1112\/jlms.12127"},{"key":"S0963548318000548_ref11","first-page":"133","article-title":"\u00dcber eine Klassifikation der Streckenkomplexe","volume":"88","author":"Hadwiger","year":"1943","journal-title":"Vierteljschr. Naturforsch. Ges. Z\u00fcrich"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548318000548","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,26]],"date-time":"2020-11-26T06:27:30Z","timestamp":1606372050000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548318000548\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,2,4]]},"references-count":31,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2019,9]]}},"alternative-id":["S0963548318000548"],"URL":"https:\/\/doi.org\/10.1017\/s0963548318000548","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,2,4]]}}}