Proof of the Clustered Hadwiger Conjecture

arXiv2306.06224MaRDI QIDQ6439845

David R. Wood, Pat Morin, Vida Dujmović, Louis Esperet

Publication date: 9 June 2023

Abstract: Hadwiger's Conjecture asserts that every $K_h$-minor-free graph is properly $(h-1)$-colourable. We prove the following improper analogue of Hadwiger's Conjecture: for fixed $h$, every $K_h$-minor-free graph is $(h-1)$-colourable with monochromatic components of bounded size. The number of colours is best possible regardless of the size of monochromatic components. It solves an open problem of Edwards, Kang, Kim, Oum and Seymour [emph{SIAM J. Disc. Math.} 2015], and concludes a line of research initiated in 2007. Similarly, for fixed $tgeqs$, we show that every $K_{s,t}$-minor-free graph is $(s+1)$-colourable with monochromatic components of bounded size. The number of colours is best possible, solving an open problem of van de Heuvel and Wood [emph{J.~London Math. Soc.} 2018]. We actually prove a single theorem from which both of the above results are immediate corollaries. For an excluded apex minor, we strengthen the result as follows: for fixed $tgeqsgeq3$, and for any fixed apex graph $X$, every $K_{s,t}$-subgraph-free $X$-minor-free graph is $(s+1)$-colourable with monochromatic components of bounded size. The number of colours is again best possible.

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

This page was built for publication: Proof of the Clustered Hadwiger Conjecture

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6439845)