New heuristics for the vertex coloring problem based on semidefinite programming

The Lovász theta number Lovász (IEEE Trans Inf Theory 25:1–7, 1979) is a well-known lower bound on the chromatic number of a graph (G), and (varPsi _K(G)) is its impressive strengthening Gvozdenovi? and Laurent (SIAM J Optim 19(2):592–615, 2008). The bound (varPsi _K(G)) was introduced in very specific and abstract setting which is tough to translate into usual mathematical programming framework. In the first part of this paper we unify the motivations and approaches to both bounds and rewrite them in a very similar settings which are easy to understand and straightforward to implement. In the second part of the paper we provide explanations how to solve efficiently the resulting semidefinite programs and how to use optimal solutions to get good coloring heuristics. We propose two vertex coloring heuristics based on (varPsi _K(G)) and present numerical results on medium sized graphs.