{"id":"arxiv/2610.39753","url":"https://arxiv.org/abs/2610.39753","tags":["cs.DS","cs.CG","cs.DM","math.CO"],"score":0,"title":"Four-Coloring Planar Graphs in Linear Time","domain":"cs.DS","source":"arxiv","authors":["Yuta Inoue","Ken-ichi Kawarabayashi","Atsuyuki Miyashita","Bojan Mohar","Carsten Thomassen","Mikkel Thorup"],"reviews":0,"subject":"cs.DS","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-29","reactions":{}}