3 papers
cs.DS2026
Four-Coloring Planar Graphs in Linear Time
Yuta Inoue, Ken-ichi Kawarabayashi, Atsuyuki Miyashita +3
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 s…
cs.DS2026
Connectivity augmentation is fixed-parameter tractable
Tuukka Korhonen, Mikkel Thorup
In the vertex connectivity augmentation problem, we are given an undirected -vertex graph , a set of links , and integers and…
math.CO2026
The Four Color Theorem with Linearly Many Reducible Configurations and Near-Linear Time Coloring
Yuta Inoue, Ken-ichi Kawarabayashi, Atsuyuki Miyashita +3
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 ach…