## Abstract

Hadwiger's conjecture asserts that every K_{t}-minor-free graph has a proper (t-1) -colouring. We relax the conclusion in Hadwiger's conjecture via improper colourings. We prove that every K_{t} -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 K_{t} -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 K_{s,t} -minor-free graphs, which lead to improved bounds on generalised colouring numbers for these classes. Finally, we prove that graphs containing no K_{t} -immersion are 2-colourable with bounded monochromatic degree.

Original language | English |
---|---|

Pages (from-to) | 129-148 |

Number of pages | 20 |

Journal | Journal of the London Mathematical Society |

Volume | 98 |

Issue number | 1 |

DOIs | |

Publication status | Published - 1 Aug 2018 |

## Keywords

- 05C15 (primary)
- 05C83 (secondary)