The Balanced Four-Color Theorem
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.
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2607.13025
curl -X POST /api/v1/records/arxiv/2607.13025/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2607.13025/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'