Hadwiger's conjecture asserts that every Kt-minor-free graph has a proper (t-1) -colouring. We relax the conclusion in Hadwiger's conjecture via improper colourings. We prove that every Kt -minor-free graph is (2t − 2)-colourable with monochromatic components of order at most 1/2 (t − 2). This result has no more colours and much smaller monochromatic components than all previous results in this direction. We then prove that every Kt -minor-free graph is (t − 1) -colourable with monochromatic degree at most t − 2. This is the best known degree bound for such a result. Both these theorems are based on a decomposition method of independent interest. We give analogous results for Ks,t -minor-free graphs, which lead to improved bounds on generalised colouring numbers for these classes. Finally, we prove that graphs containing no Kt -immersion are 2-colourable with bounded monochromatic degree.
- 05C15 (primary)
- 05C83 (secondary)