{"id":"arxiv/2607.13025","url":"https://arxiv.org/abs/2607.13025","tags":["cs.DS","math.CO"],"score":0,"title":"The Balanced Four-Color Theorem","domain":"cs.DS","source":"arxiv","authors":["Ken-ichi Kawarabayashi","Hirotaka Yoneda","Masataka Yoneda"],"reviews":0,"subject":"cs.DS","summary":"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.","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-07-14","reactions":{}}