The Balanced Four-Color Theorem

Ken-ichi Kawarabayashi; Hirotaka Yoneda; Masataka Yoneda

graph theory

The Balanced Four-Color Theorem

arXiv:2607.13025

summary

The paper proves that every planar graph with at least three vertices can be 4‑colored so that each color class contains fewer than half of the vertices, and provides an O(n log n) algorithm to find such a coloring, with extensions to more colors and graphs on other surfaces.

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 lo g n)$ time. We also extend these results to five or more colors and to graphs on general surfaces.

Topics & keywords

#planar graphs #graph coloring #balanced coloring #algorithmic complexity #surface embeddingsfour-color theorembalanced 4‑coloringO(n log n) algorithmplanar graphgraph coloring algorithmcombinatorial optimization