Four-Coloring Planar Graphs in Linear Time
Authors: Yuta Inoue, Ken-ichi Kawarabayashi, Atsuyuki Miyashita, Bojan Mohar, Carsten Thomassen, Mikkel Thorup
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 papers around it, by date and closeness
Higher is closer to this paper; left is older. Lines join papers close to each other: groups of lines are sub-topics. Select a point to see why it is there. Back to the summary of this paper
Papers around this one
Ranked by how close their title and abstract are to this paper’s. Select some to read them together.
Closest papers
-
Three-coloring triangle-free planar graphs in linear timeZ. Dvořák, K. Kawarabayashi, R. Thomas · 2009 · TALG · cited 45 times · Not summarized yet
Three-coloring triangle-free planar graphs in linear time finds a 3-coloring in linear time, whereas this paper constructs a 4-coloring of general planar graphs.
Abstract
Grötzsch's theorem states that every triangle-free planar graph is 3-colorable, and several relatively simple proofs of this fact were provided by Thomassen and other authors. It is easy to convert these proofs into quadratic-time algorithms to find a 3-coloring, but it is not clear how to find such a coloring in linear time (Kowalik used a nontrivial data structure to construct an O(n log n) algorithm). We design a linear-time algorithm to find a 3-coloring of a given triangle-free planar graph. The algorithm avoids using any complex data structures, which makes it easy to implement. As a by-product, we give a yet simpler proof of Grötzsch's theorem.
-
Efficiently four-coloring planar graphsN. Robertson, Daniel P. Sanders, P. Seymour et al. · 1996 · Symposium on the Theory of Computing · cited 124 times · Not summarized yet
Efficiently four-coloring planar graphs addresses the construction of four-colorings for planar graphs, the same task studied here.
-
Three-coloring triangle-free planar graphs in linear time (extended abstract)Z. Dvořák, Ken-ichi Kawarabayashi, Robin Thomas · 2009 · cited 1 time · Not summarized yet
Three-coloring triangle-free planar graphs in linear time (extended abstract) concerns finding linear-time 3-colorings of triangle-free planar graphs, rather than four-colorings of general planar graphs.
-
Deciding 4-colorability of planar triangulationsM. Loebl · 2015 · arXiv.org · preprint, not peer reviewed · cited 1 time · Not summarized yet
Deciding 4-colorability of planar triangulations tests whether four-colorings exist, while this paper constructs one for planar graphs.
Abstract
We show, without using the Four Color Theorem, that for each planar triangulation, the number of its proper vertex colorings by 4 colors is a determinant and thus can be calculated in a polynomial time. In particular, we can efficiently decide if the number is non-zero.
-
A simple algorithm for 4-coloring 3-colorable planar graphsK. Kawarabayashi, K. Ozeki · 2010 · Theoretical Computer Science · cited 6 times · Not summarized yet
A simple algorithm for 4-coloring 3-colorable planar graphs constructs four-colorings for a restricted class of planar graphs.
-
Every Planar Map Is Four ColorableK. Appel, W. Haken · 2019 · Mathematical Solitaires & Games · cited 656 times · Not summarized yet
Every Planar Map Is Four Colorable establishes the four-colorability theorem and discusses reducibility, the theoretical basis for this algorithm.
Abstract
As has become standard, the four color map problem will be considered in the dual sense as the problem of whether the vertices of every planar graph (without loops) can be colored with at most four colors in such a way that no pair of vertices which lie on a common edge have the same color. The restriction to triangulations with all vertices of degree at least five is a consequence of the work of A. B. Kempe. Over the past 100 years, a number of authors including A. B. Kempe, G. D. Birkhoff, and H. Heesch have developed a theory of reducibility to attack the problem. Simultaneously, a theory of unavoidable sets has been developed and the fusion of these has led to the proof. A configuration …
-
3-Coloring in Time O(1.3217^n)Lucas Meijer · 2023 · arXiv.org · preprint, not peer reviewed · cited 16 times · Not summarized yet
3-Coloring in Time O(1.3217^n) studies an exponential-time 3-coloring algorithm, unlike this paper’s linear-time planar four-coloring problem.
Abstract
We propose a new algorithm for 3-coloring that runs in time O(1.3217^n). For this algorithm, we make use of the time O(1.3289^n) algorithm for 3-coloring by Beigel and Eppstein. They described a structure in all graphs, whose vertices could be colored relatively easily. In this paper, we improve upon this structure and present new ways to determine how the involved vertices reduce the runtime of the algorithm.
-
Drawing 2-, 3- and 4-colorable Graphs in O(n2) VolumeT. Calamoneri, Andrea Sterbini · 1996 · International Symposium Graph Drawing and Network Visualization · cited 15 times · Not summarized yet
Drawing 2-, 3- and 4-colorable Graphs in O(n2) Volume studies graph drawings with colorability constraints, rather than constructing planar graph colorings.
Prior work it builds on
-
Structured recursive separator decompositions for planar graphs in linear timeP. Klein, S. Mozes, Christian Sommer · 2012 · Symposium on the Theory of Computing · cited 92 times · Not summarized yet
Structured recursive separator decompositions for planar graphs in linear time computes recursive planar r-divisions, a data structure used by this paper.
Abstract
Given a triangulated planar graph G on n vertices and an integer rr--division of G with few holes is a decomposition of G into O(n/r) regions of size at most r such that each region contains at most a constant number of faces that are not faces of G (also called holes), and such that, for each region, the total number of vertices on these faces is O(√ r). We provide an algorithm for computing r--divisions with few holes in linear time. In fact, our algorithm computes a structure, called decomposition tree, which represents a recursive decomposition of G that includes r--divisions for essentially all values of r. In particular, given an exponentially increasing sequence {vec r} = (r1,r2,...),…
-
EVERY PLANAR MAP IS FOUR COLORABLERobin J. Wilson · 1991 · Bulletin of The London Mathematical Society · cited 319 times · Not summarized yet
EVERY PLANAR MAP IS FOUR COLORABLE presents the Four Color Theorem that this paper’s coloring algorithm makes constructive.
-
The Four-Color ProblemK. Appel, W. Haken · 1978 · cited 254 times · Not summarized yet
The Four-Color Problem discusses the four-color problem that this paper addresses algorithmically.
-
An unavoidable set of D-reducible configurationsJ. Steinberger · 2009 · arXiv: Combinatorics · preprint, not peer reviewed · cited 11 times · Not summarized yet
An unavoidable set of D-reducible configurations proves the Four Color Theorem using configurations that this paper’s algorithm builds on.
Abstract
We give a new proof of the four-color theorem by exhibiting an unavoidable set of 2822 D-reducible configurations. The existence of such a set had been conjectured by several researchers including Stromquist, Appel and Haken, and Robertson, Sanders, Seymour and Thomas.
-
Fast Algorithms for Shortest Paths in Planar Graphs, with ApplicationsG. Frederickson · 1987 · SIAM journal on computing (Print) · cited 492 times · Not summarized yet
Fast Algorithms for Shortest Paths in Planar Graphs, with Applications provides planar-graph algorithmic techniques cited by this paper.
Go further
How are these papers found?
We compare the title and abstract of this paper with those of every paper summarized on this site, and with the papers Semantic Scholar recommends, those it cites and those citing it (for a much-cited paper, its most recent citations and, from OpenAlex, the most cited ones). Among the prior work and the follow-ups, the papers that use each other in depth, a method it uses and the much-cited follow-ups come a little higher. The levels (very close, close, related) come from the similarity of the texts, not from a judgment of quality; * marks a paper without an abstract, compared by its title. The sentence under a paper is written by an AI from the two abstracts: check it in the papers. A paper marked not relevant by three readers leaves the list.
Updated on 2 November 2026.