Approximate graph coloring by semidefinite programming

We consider the problem of coloring k-colorable graphs with the fewest possible colors. We give a randomized polynomial time algorithm which colors a 3-colorable graph on n vertices with min {O(Δ^1/3log^4/3Δ), O(n^1/4 log n)} colors where Δ is the maximum degree of any vertex. Besides giving the best known approximation ratio in terms of n, this marks the first non-trivial approximation result as a function of the maximum degree Δ. This result can be generalized to k-colorable graphs to obtain a coloring using min {O˜(Δ^1-2k/), O˜(n^1-3(k+1/))} colors. Our results are inspired by the recent work of Goemans and Williamson who used an algorithm for semidefinite optimization problems, which generalize linear programs, to obtain improved approximations for the MAX CUT and MAX 2-SAT problems. An intriguing outcome of our work is a duality relationship established between the value of the optimum solution to our semidefinite program and the Lovasz ϑ-function. We show lower bounds on the gap between the optimum solution of our semidefinite program and the actual chromatic number; by duality this also demonstrates interesting new facts about the ϑ-function