APPROXIMATE GRAPH-COLORING BY SEMIDEFINITE PROGRAMMING

We consider the problem of coloring k-colorable graphs with the fewest possible colors. We present a randomized polynomial time algorithm th at colors a 3-colorable graph on n vertices with min {O(Delta(1/3) log (1/2) Delta log n), O(n(1/4) log(1/2) n)} colors where Delta is the ma ximum degree of any vertex. Besides giving the best known approximatio n ratio in terms of n, this marks the first nontrivial approximation r esult as a function of the maximum degree Delta. This result can be ge neralized to k-colorable graphs to obtain a coloring using min {O(Delt a(1-2/k) log(1/2) Delta log n), O(n(1-3/(k+1)) log(1/2) n)} colors. Ou r results are inspired by the recent work of Goemans and Williamson wh o used an algorithm for semidefinite optimization problems, which gene ralize linear programs, to obtain improved approximations for the MAX CUT and MAX 2-SAT problems. An intriguing outcome of our work is a dua lity relationship established between the value of the optimum solutio n to our semidefinite program and the Lovasz theta-function. We show l ower bounds on the gap between the optimum solution of our semidefinit e program and the actual chromatic number; by duality this also demons trates interesting new facts about the theta-function.