Approximate graph coloring by semidefinite programming

Abstract

We consider the problem of coloring k -colorable graphs with the fewest possible colors. We present a randomized polynomial time algorithm that colors a 3-colorable graph on n vertices with min{ O (Δ 1/3 log 1/2 Δ log n ), O ( n 1/4 log 1/2 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 nontrivial 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-2/ k log 1/2 Δ log n ), O ( n 1−3/( k +1) log 1/2 n )} 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 Lovász θ-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.