Four-Coloring Planar Graphs in Linear Time
The famous Four Color Theorem (4CT) states that any planar graph can be colored with four colors, but how do we find a 4-coloring? In our previous paper [FOCS'26], we presented a simple combinatorial algorithm to 4-color planar graphs in $O(n\log n)$ time. We improve it here to $O(n)$ time, which is optimal. The algorithm from our previous paper is based on proving that every planar triangulation has a linear number of reducible configurations or obstructing cycles. The bottleneck for the algorithm is that we need $O(\log n)$ Kempe changes to extend a recursive 4-coloring to the reducible…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.39753
curl -X POST /api/v1/records/arxiv/2610.39753/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.39753/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'