Coloring planar graphs with three colors and no large monochromatic components

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.

v3: fixed a notation issue in Section 3

Cited by in corpus (11)

• Improper Colourings inspired by Hadwiger's Conjecture
• Clustered 3-Colouring Graphs of Bounded Degree
• Partitioning $H$-minor free graphs into three subgraphs with no large components
• Clustered Variants of Hajós' Conjecture
• Minor-closed graph classes with bounded layered pathwidth
• Islands in graphs on surfaces
• Improper coloring of graphs with no odd clique minor
• Clustered Coloring of Graphs with Bounded Layered Treewidth and Bounded Degree
• Colouring Strong Products
• The grid-minor theorem revisited
• Weak diameter choosability of graphs with an excluded minor