The Balanced Four-Color Theorem

We show that every planar graph with $n \geq 3$ vertices admits a 4-coloring in which each color is used on fewer than $n/2$ vertices.

This bound is the best possible.

Moreover, such a coloring can be found in $O(n \log n)$ time.

We also extend these results to five or more colors and to graphs on general surfaces.