Approximate graph coloring by semidefinite programming
We consider the problem of coloring <italic>k</italic>-colorable graphs with the fewest possible colors. We present a randomized polynomial time algorithm that colors a 3-colorable graph on <italic>n</italic> vertices with min{<italic>O</italic>(Δ<supscrpt>1/3</supscrpt> log<supscrpt>1/2</supscrpt> Δ log <italic>n</italic>), <italic>O</italic>(<italic>n</italic><supscrpt>1/4</supscrpt> log<supscrpt>1/2</supscrpt> <italic>n</italic>)} colors where Δ is the maximum degree of any vertex. Besides giving the best known approximation ratio in terms of <italic>n</italic>, this marks the first nontrivial approximation result as a function of the maximum degree Δ. This result can be generalized to <italic>k</italic>-colorable graphs to obtain a coloring using  min{<italic>O</italic>(Δ<supscrpt>1-2/<italic>k</italic></supscrpt> log<supscrpt>1/2</supscrpt> Δ log <italic>n</italic>), <italic>O</italic>(<italic>n</italic><supscrpt>1−3/(<italic>k</italic>+1)</supscrpt> log<supscrpt>1/2</supscrpt> <italic>n</italic>)} colors. Our results are inspired by the recent work of Goemans and Williamson who used an algorithm for <italic>semidefinite optimization problems</italic>, 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 &thgr;-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 &thgr;-function.