arXiv preprint ·
Four-Coloring Planar Graphs in Linear Time
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
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 configurations. Each Kempe change can involve a constant fraction of the graph and takes linear time. Here we show that all $O(\log n)$ Kempe changes can be identified and implemented in $O(n)$ time. The idea is to spend $O(n)$ time to preprocess the graph so that we can identify and simulate each good Kempe change in $O(n/\log n)$ amortized time. Thus, we implement all $O(\log n)$ Kempe changes in $O(n)$ total time. Based on this, we implement the whole 4-coloring in linear time. We note that creating such a representation for fast identification and simulation of the right Kempe changes is a challenge of data structures, unlike the previous paper that builds on a new graph theoretic understanding of reducible configurations.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
PhysicsNeMo-Mesh: GPU-Native Meshes and Simulation Cases for Physics AI
Optimal Average Distortion for Non-Expansive Embeddings of Euclidean Metrics into the Line: With applications to cut-matching games and vertex expansion
Implicit Additively Weighted Geodesic Voronoi Diagrams and Applications
Compressed Orientation Reachability Maps for Sub-Second Robotic Needle Entry Point Planning
Catenary Visibility: A Geometric Framework for Planning with Tethered Robots
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.