The Balanced Four-Color Theorem
2026-07-14 • Data Structures and Algorithms
Data Structures and Algorithms
AI summaryⓘ
The authors show that for any planar graph with at least three points, you can color it using four colors in a way that no color is used on half or more of the points. This limit on color group size is the best you can do. They also provide a method to find such a coloring quickly, in about n log n steps. Additionally, they extend these findings to cases with five or more colors and to graphs drawn on other surfaces beyond the plane.
planar graphgraph coloring4-color theoremalgorithm complexitygraph theorysurface graphscoloring algorithmn log n time
Authors
Ken-ichi Kawarabayashi, Hirotaka Yoneda, Masataka Yoneda
Abstract
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.