Four-Coloring Planar Graphs in Linear Time

Yuta Inoue; Ken-ichi Kawarabayashi; Atsuyuki Miyashita; Bojan Mohar; Carsten Thomassen; Mikkel Thorup

AI summary · arXiv: 2610.39753v1 · cs.DS

Four-Coloring Planar Graphs in Linear Time

Yuta Inoue, Ken-ichi Kawarabayashi, Atsuyuki Miyashita, Bojan Mohar, Carsten Thomassen, Mikkel Thorup

Original paper Submitted to arXiv on 29 Oct. 2026 License: CC BY 4.0 Also in: fr

How to read this summary? Illustrated guide

The essentials

The paper proves that planar graphs can be four-colored deterministically in optimal linear time by accelerating Kempe changes using compact planar encodings and tabulation.

Question

How can a four-coloring of an n-vertex planar graph be constructed in optimal linear time? The paper addresses the Kempe-change bottleneck in the authors’ previous O(n log n) algorithm.

Method

This theoretical algorithm builds on previously established families of non-touching D-reducible configurations, with maximum ring size 18 and maximum reducibility level 25. It combines recursive r-divisions, compact planar graph encodings, and tabulation of subproblems encoded in half-logarithmic numbers of bits, using a word RAM with word length proportional to log n. Conditional expectations select deterministic Kempe changes, while segmented counter transfers handle information too large for a single table lookup.

Findings

Result The authors prove a deterministic O(n)-time algorithm for four-coloring any n-vertex planar graph.
See the passage in the paper
We can 4-color a planar graph of order $n$ in $O(n)$ time.
Result Linear-time preprocessing enables identification and simulation of all O(log n) required Kempe changes in O(n) total time.
See the passage in the paper
The idea is to spend $O(n)$ time to preprocess the graph, including the selection of an appropriate subfamily ${\mathcal{Z}}^{\prime}$, so that we can identify and simulate each Kempe change in $O(n/\log n)$ amortized time. Thus, we implement all $O(\log n)$ Kempe changes in $O(n)$ total time.
Result Each deterministic Kempe-change step improves at least a fraction 1/(3 × 2^18) of the participating rings in O(n/log n) time.
See the passage in the paper
We can then, deterministically in $O(n/\log n)$ time, find and execute a Kempe change that is improving for at least a fraction $p=\frac{1}{3\cdot 2^{18}}$ of the rings, and also tell which rings got improved.
Authors’ interpretation The authors attribute the improvement over their previous algorithm to data structures rather than new graph-theoretic foundations.
See the passage in the paper
We note that creating such a representation for fast identification and simulation of good Kempe changes is a challenge of data structures, unlike [9], which focused on a new graph theoretic understanding of reducible configurations.

Limitations

The running-time guarantee is established for a specified word RAM model, rather than independently of the computational model.
See the passage in the paper
More precisely, we use the word RAM model with word length $\Theta(\log n)$.
Determining improving changes relies on storing ring-coloring levels whose information requirements have a very large constant.
See the passage in the paper
This is a huge constant amount of information, but we need it to determine if a given Kempe change will improve.

Why it matters

The paper improves the authors’ previous O(n log n) construction to an optimal O(n) algorithm for planar four-coloring. Its contribution shows how compact planar representations and carefully organized tabulation can remove the logarithmic overhead of repeated, potentially graph-wide Kempe changes.

Written by AI from the paper. Passages are checked word for word against the text we analysed; the rest may contain errors.

AI-generated keywords: Four Color Theorem; Planar graphs; Linear-time algorithms; Kempe changes; Recursive planar divisions

Read further

Comprehensive Summary
Layman's Summary
Blog article
Original abstract

This paper addresses the algorithmic question behind the Four Color Theorem: how efficiently can a proper four-coloring of a planar graph be constructed? Although the theorem guarantees that four colors suffice, finding such a coloring efficiently has historically been challenging. The authors present a deterministic O(n)-time algorithm for an n-vertex planar graph, improving on their previous O(n log n) algorithm and an earlier quadratic-time bound. Linear time is asymptotically optimal because explicitly outputting the vertex colors requires Ω(n) time. The improvement is primarily data-structural rather than a new graph-theoretic proof of four-colorability. The algorithm builds on the authors’ earlier result that, in linear time, every planar triangulation yields either linearly many pairwise non-touching induced D-reducible configurations or linearly many non-touching obstructing cycles. The configurations belong to a fixed family of 8,202 possibilities, have rings containing at most 18 vertices, and require at most 25 improving Kempe changes to make any ring coloring extendible. Every vertex in these configurations or obstructing cycles has degree at most 12. A Kempe change swaps two colors within selected connected components induced by a pair of colors, preserving the validity of the coloring. Removing many configurations allows recursion on a graph smaller by a constant factor. However, restoring their colors previously required O(log n) Kempe changes, each potentially taking linear time. The central advance is a method for identifying and executing these changes in O(n) total time after linear preprocessing. The authors construct recursive planar r-divisions whose regions contain at most r vertices and have boundaries of size O(√r). They retain a linear-size subfamily of configurations lying strictly inside leaf regions of size proportional to log n. Compact encodings of planar graphs and relevant boundary structures allow sufficiently small subproblems to be solved using precomputed lookup tables. Each encoding uses at most half of log n bits, yielding at most √n table indices. Total table construction time and space are bounded by √n times polylogarithmic factors. Kempe connectivity is represented by contracting appropriate components inside boundary faces while preserving a planar graph whose size is proportional to the boundary size. Bottom-up and top-down passes recover the connectivity information needed within each region. Packed color representations then allow all colors in a leaf region to be updated with a single lookup. Together, these techniques reduce the time needed to identify connectivity and execute a Kempe change to O(n/log n). The most difficult step is selecting effective changes deterministically. The method of conditional expectations guarantees a change that improves at least a 1/(3 · 2¹⁸) fraction of the participating rings. Planarity bounds the number of distinct configuration-interaction types by a constant multiple of the number of relevant Kempe chains, and counts of these types support efficient selection. When counter arrays exceed the lookup-table budget, the algorithm partitions them into segments and transfers information using pairs of segments. This enables deterministic selection in O(n/log n) time per change, yielding linear-time color extension and, through recursion, linear-time coloring overall. The result is theoretical: the paper provides neither an implementation nor an experimental evaluation. It assumes a word RAM with word length proportional to log n and standard addressing, arithmetic, bitwise, and shift operations. The fixed configuration family, exhaustive ring-coloring information, and small guaranteed improvement fraction introduce potentially enormous constants. Thus, the paper establishes an optimal asymptotic bound without demonstrating practical speed. Its conclusions also rely on earlier structural results, and the appendix clarifies and repairs aspects of the recursive-division machinery used in the analysis.

Four-Coloring Planar Graphs in Linear Time: An Optimal Algorithm, at Last

The Four Color Theorem promises that every planar graph can be colored with just four colors, with no two adjacent vertices sharing a color. But a guarantee that a coloring exists is not the same as a fast recipe for finding one. How efficiently can an algorithm actually assign those colors?

“Four-Coloring Planar Graphs in Linear Time,” by Yuta Inoue, Ken-ichi Kawarabayashi, Atsuyuki Miyashita, Bojan Mohar, Carsten Thomassen, and Mikkel Thorup, answers that question with a deterministic O(n)-time algorithm for a planar graph with n vertices. This improves on the authors’ previous O(n log n) algorithm and an earlier quadratic-time bound.

Linear time is asymptotically optimal: simply writing down one color for each vertex already requires Ω(n) time. The achievement is therefore a theoretical endpoint for this problem’s running-time growth, though not necessarily a practical coloring tool.

The Challenge: Putting Removed Pieces Back

The new result is primarily a data-structural breakthrough, rather than a new graph-theoretic proof of four-colorability. Its foundation is an earlier structural result: in linear time, a planar triangulation yields either linearly many pairwise non-touching induced D-reducible configurations or linearly many non-touching obstructing cycles.

The reducible configurations come from a fixed family of 8,202 possibilities. Each has a surrounding ring containing at most 18 vertices, and every vertex in the configurations or obstructing cycles has degree at most 12. These bounded sizes make local reasoning possible, even within a very large graph.

The recursive strategy is to remove many suitable configurations, color a graph smaller by a constant factor, and then restore the removed pieces. The difficult part is restoration: the colors already assigned to a configuration’s ring might not extend to its interior.

Kempe Changes: Safe but Potentially Expensive

A Kempe change selects connected components formed by two colors and swaps those colors within them. Because the swap preserves a proper coloring, it can rearrange the surrounding colors without introducing conflicts. For these configurations, at most 25 improving Kempe changes suffice to make any ring coloring extendible.

However, what looks like a local repair may depend on connectivity far across the graph. Earlier methods needed O(log n) Kempe changes during restoration, with each change potentially costing linear time. The new paper removes that bottleneck by making connectivity queries, recoloring, and deterministic selection collectively efficient.

Breaking the Graph into Table-Sized Pieces

The authors organize the graph using recursive planar r-divisions. Each region contains at most r vertices and has a boundary of size O(√r). They retain a linear-size subfamily of configurations lying strictly inside leaf regions whose sizes are proportional to log n.

This creates small regions that can be handled through precomputed lookup tables. The key is compact encoding: the relevant planar graphs and boundary structures are represented using at most half of log n bits per encoding. That leaves at most √n possible table indices, with total table construction time and space bounded by √n times polylogarithmic factors.

The tables replace repeated small computations with direct lookups. Packed color representations also allow all colors within a leaf region to be updated through a single lookup.

Keeping Track of Connectivity Beyond a Region

A small region cannot be treated as isolated. Two vertices on its boundary might belong to the same two-color component through a path outside it. Missing that connection could lead to an incorrect Kempe change.

To preserve this information, the algorithm contracts appropriate components inside boundary faces, maintaining a planar representation whose size is proportional to the boundary size. Bottom-up and top-down passes through the recursive division recover the connectivity information each region needs. Together with lookup tables and packed colors, this reduces connectivity identification and execution of a Kempe change to O(n/log n) time.

Choosing Useful Changes Deterministically

Fast execution is only part of the solution. The algorithm must also choose changes that improve enough rings. Its most difficult step uses the method of conditional expectations to guarantee a change that improves at least a 1/(3 · 2¹⁸) fraction of participating rings.

Planarity limits the number of distinct configuration-interaction types to a constant multiple of the relevant Kempe chains. Counting these types supports efficient selection. When the required counter arrays exceed the lookup-table budget, the algorithm divides them into segments and transfers information using pairs of segments.

This machinery achieves deterministic selection in O(n/log n) time per change. Across O(log n) changes, color extension takes linear time. Recursing on graphs that shrink by a constant factor then gives an overall O(n) bound.

What the Result Does—and Does Not—Establish

The paper establishes an optimal asymptotic running time, not demonstrated practical speed. Important qualifications include:

No implementation or experimental evaluation is provided.
The analysis assumes a word RAM with word length proportional to log n and standard addressing, arithmetic, bitwise, and shift operations.
The fixed configuration family, exhaustive ring-coloring information, and tiny guaranteed improvement fraction can introduce enormous constants.
The argument relies on earlier structural results, while an appendix clarifies and repairs aspects of the recursive-division machinery.

The central lesson is nevertheless striking: the final obstacle was not proving that four colors suffice, but managing connectivity and recoloring efficiently enough. By combining planar structure, compact representations, and deterministic selection, the authors bring the construction time down to the unavoidable cost of producing the answer.

Created on 02 Nov. 2026

Was this synthesis useful?

Score: 0

Ask questions about this paper to our AI assistant

How to chat with this paper? Illustrated guide

Compare with the PDF

You can also chat with multiple papers at once here.

AI assistant instructions?

Tools for this paper

Explain it differently 3 free rewrites left today

Save to a collection Group papers in collections to compare them, chat with them and export them. Create a free account Log in

Export BibTeX · RIS (Zotero, Mendeley, EndNote) · Obsidian (Markdown) · Notion (Markdown)

Advanced tools Premium

For researchers who follow a field closely: citation alerts, journal-club slides, version comparison and Zotero export. Discover Premium

Zotero

Citation alerts Citation alerts guide

Who works on it? The people and institutions who publish on its topic

Weekly letter Presented in "Computing beyond AI this week" of 2 November 2026. Computing beyond AI this week: Better algorithms, smaller machines, harder tests

Journal club Premium+ Slides to present it Propose for the journal club

Versions What changed between versions

Talk about it in public Premium+ Press kit: release, questions, hype check Press kit guide

Disclaimer: The AI-based summarization tool and virtual assistant provided on this website may not always provide accurate and complete summaries or responses. We encourage you to carefully review and evaluate the generated content to ensure its quality and relevance to your needs.

Four-Coloring Planar Graphs in Linear Time

The essentials

Question

Method

Findings

Limitations

Why it matters

Read further

Definitions

Four-Coloring Planar Graphs in Linear Time: An Optimal Algorithm, at Last

The Challenge: Putting Removed Pieces Back

Kempe Changes: Safe but Potentially Expensive

Breaking the Graph into Table-Sized Pieces

Keeping Track of Connectivity Beyond a Region

Choosing Useful Changes Deterministically

What the Result Does—and Does Not—Establish

Ask questions about this paper to our AI assistant

Tools for this paper

Advanced tools Premium

Papers around this one

Closest papers

Prior work it builds on

Go further

Cite this paper (BibTeX)