Colouring Planar Graphs With Three Colours and No Large Monochromatic Components
- 1 April 2014
- journal article
- research article
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 23 (4) , 551-570
Abstract
We prove the existence of a function $f :\mathbb{N} \to \mathbb{N}$ such that the vertices of every planar graph with maximum degree Δ can be 3-coloured in such a way that each monochromatic component has at mostf(Δ) vertices. This is best possible (the number of colours cannot be reduced and the dependence on the maximum degree cannot be avoided) and answers a question raised by Kleinberg, Motwani, Raghavan and Venkatasubramanian in 1997. Our result extends to graphs of bounded genus.
Keywords
All Related Versions
This publication has 11 references indexed in Scilit:
- From the plane to higher surfacesJournal of Combinatorial Theory, Series B, 2012
- Contractibility and the Hadwiger ConjectureEuropean Journal of Combinatorics, 2010
- Graph Colouring with No Large Monochromatic ComponentsCombinatorics, Probability and Computing, 2008
- A relaxed Hadwiger's Conjecture for list coloringsJournal of Combinatorial Theory, Series B, 2007
- Bounded size components—partitions and transversalsJournal of Combinatorial Theory, Series B, 2003
- Partitioning into graphs with only small componentsJournal of Combinatorial Theory, Series B, 2003
- Storage management for evolving databases2002
- Low diameter graph decompositionsCombinatorica, 1993
- Lower bound of the hadwiger number of graphs by their average degreeCombinatorica, 1984
- An extremal function for contractions of graphsMathematical Proceedings of the Cambridge Philosophical Society, 1984