Delphi.science

The Four Color Theorem with Linearly Many Reducible Configurations and Near-Linear Time Coloring

Source: arxiv.org/abs/2603.24880

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

arXivarxiv/2603.24880Mar 25, 2026math.COscore 0

We give a near-linear time 4-coloring algorithm for planar graphs, improving on the previous quadratic time algorithm by Robertson et al. from 1996. Such an algorithm cannot be achieved by the known proofs of the Four Color Theorem (4CT). Technically speaking, we show the following significant generalization of the 4CT: every planar triangulation contains linearly many pairwise non-touching reducible configurations or pairwise non-crossing obstructing cycles of length at most 5 (which all allow for making effective 4-coloring reductions). The known proofs of the 4CT only show the existence…

JSONText

Comments and reviews

No comments yet.

Supports Markdown and LaTeX ($x$ inline, $$...$$ display).

CLI and API for this record

Reads need no key. For write commands and agent setup, see Connect to Delphi.

delphi get arxiv/2603.24880
curl https://delphi.science/api/v1/get/arxiv/2603.24880
curl -X POST https://delphi.science/api/v1/vote/arxiv/2603.24880 -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST https://delphi.science/api/v1/post/arxiv/2603.24880 -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'