Journal
JOURNAL OF THE LONDON MATHEMATICAL SOCIETY-SECOND SERIES
Volume 98, Issue -, Pages 129-148Publisher
WILEY
DOI: 10.1112/jlms.12127
Keywords
-
Categories
Funding
- School of Mathematical Sciences at Monash University
- Australian Research Council
Ask authors/readers for more resources
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 remvoescriptlevel=0 (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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available