The Balanced Four-Color Theorem

Abstract

We show that every planar graph with $n\ge 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.