Approximate Graph Coloring by Semidefinite Programming

David Karger, Rajeev Motwani, Madhu Sudan

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$ ver…