Four-Coloring Planar Graphs in Linear Time
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(nlog 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.
Related
- Bounds for B-coloring planar and outerplanar graphs
- Total-coloring of planar graphs with maximum degree 6 and without prescribed 4-cycles
- The Borowiecki-Broere Generalized Total Coloring Conjecture for Planar Graphs
- Bounds for B-coloring planar and outerplanar graphs
- Frugal coloring in planar graphs with maximum degree 4 and 5
BibTeX
@misc{inoue2026fourcoloring,
title = {{Four-Coloring Planar Graphs in Linear Time}},
author = {Yuta Inoue and Ken-ichi Kawarabayashi and Atsuyuki Miyashita and Bojan Mohar and Carsten Thomassen and Mikkel Thorup},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.39753},
eprint = {2610.39753},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.39753},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Four-Coloring Planar Graphs in Linear Time
AU - Yuta Inoue
AU - Ken-ichi Kawarabayashi
AU - Atsuyuki Miyashita
AU - Bojan Mohar
AU - Carsten Thomassen
AU - Mikkel Thorup
PY - 2026
DA - 2026/10/29
PB - arXiv
DO - 10.48550/arxiv.2610.39753
UR - https://arxiv.org/abs/2610.39753
AB - 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(nlog 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.
ER -