Coloring planar graphs with three colors and no large monochromatic components

We prove the existence of a function $f:\mathbb{N}\to \mathbb{N}$ such that the vertices of every planar graph with maximum degree $\mathrm{\Delta }$ can be 3-colored in such a way that each monochromatic component has at most $f(\mathrm{\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.