{"ID":6626545,"CreatedAt":"2026-07-15T02:56:36.47817413Z","UpdatedAt":"2026-07-15T03:28:55.185153975Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.13025","arxiv_id":"2607.13025","title":"The Balanced Four-Color Theorem","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.","short_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.","url_abs":"https://arxiv.org/abs/2607.13025","url_pdf":"https://arxiv.org/pdf/2607.13025v1","authors":"[\"Ken-ichi Kawarabayashi\",\"Hirotaka Yoneda\",\"Masataka Yoneda\"]","published":"2026-07-14T17:58:34Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"math.CO\"]","methods":"[]","has_code":false}