{"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","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-03-25","reactions":{}}