Combinatorial Coloring of 3-Colorable Graphs

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 Õ(n^4/11) colors. This is the first combinatorial improvement of Blum´s Õ(n^3/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 Õ(n^0.2072) colors by Chlamtac from FOCS´07. We now bring it down to Õ(n^{0. 2049}) colors.