Coloring planar graphs with three colors and no large monochromatic components
Preprint
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 $\Delta$ can be 3-colored in such a way that each monochromatic component has at most $f(\Delta)$ vertices. This is best possible (the number of colors 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 8 references indexed in Scilit:
- 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
- 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