Improper colourings inspired by Hadwiger's conjecture

Jan van den Heuvel, David R. Wood

Research output: Contribution to journalArticleResearchpeer-review

12 Citations (Scopus)

Abstract

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.

Original languageEnglish
Pages (from-to)129-148
Number of pages20
JournalJournal of the London Mathematical Society
Volume98
Issue number1
DOIs
Publication statusPublished - 1 Aug 2018

Keywords

  • 05C15 (primary)
  • 05C83 (secondary)

Cite this