Combinatorial Coloring of 3-Colorable Graphs
Ken‐ichi Kawarabayashi, Mikkel Thorup · 2012
We consider the problem of coloring a 3-colorable graph in polynomial time using as few colors as possible. We present a combinatorial algorithm getting down to Õ(n4/11) colors. This is the first combinatorial improvement of Blum's Õ(n3/8) bound from FOCS'90. Like Blum's algorithm, our new algorithm composes nicely with recent semi-definite programming approaches. The current best bound is Õ(n0.2072) colors by Chlamtac from FOCS'07. We now bring it down to Õ(n0. 2049) colors.