2 papers
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…