2 papers
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…
math.CO2019
Partite Turán-densities for complete uniform hypergraphs on vertices
Klas Markström, Carsten Thomassen
In this paper we investigate density conditions for finding a complete -uniform hypergraph on vertices in an -partite -uniform hypergraph . Fi…