Id: arxiv/2603.24880 Url: https://arxiv.org/abs/2603.24880 Tags: math.CO, cs.CG, cs.DM, cs.DS Score: 0 Title: The Four Color Theorem with Linearly Many Reducible Configurations and Near-Linear Time Coloring Domain: math.CO Source: arxiv Authors: Yuta Inoue, Ken-ichi Kawarabayashi, Atsuyuki Miyashita, Bojan Mohar, Carsten Thomassen, Mikkel Thorup Reviews: 0 Subject: math.CO Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-03-25 Page: https://delphi.science/r/arxiv/2603.24880 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…