New heuristics for the vertex coloring problem based on semidefinite programming

The Lovász theta number Lovász (1979) is a well‐known lower bound on the chromatic number of a graph $G$ , and ${\Psi }_K(G)$ is its impressive strengthening Gvozdenović and Laurent (2008). The bound ${\Psi }_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 ${\Psi }_K(G)$ and present numerical results on medium sized graphs.