Theory Seminar, October 12th, 2:00pm
Warren Weaver Hall, Room 1314

Combinatorial Coloring of 3-Colorable Graphs

Mikkel Thorup, AT&T / University of Copenhagen

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 $\tilde O(n^{4/11})$ colors. This is the first combinatorial improvement of Blum's $\tilde O(n^{3/8})$ bound from FOCS'90. Like Blum's algorithm, our new algorithm composes nicely with recent semi-definite approaches. The current best bound is $O(n^{0.2072})$ colors by Chlamtac from FOCS'07. We now bring it down to $O(n^{0.2038})$ colors. Joint work with with Ken-Ichi Kawarabayashi.