Stable-Set and Coloring bounds based on k-ones 0-1 quadratic optimiza...

The Lovász Theta function provides a well studied tool to get bounds for the stability number and the chromatic number of graphs. It is the optimal value of a semidefinite program in matrices of order n having m equality constraints plus possibly some additional sign constraints. Here n denotes the number of vertices and m the number of edges of the underlying graph. The number m of equations may be of order quadratic in n which limits the practical use of the Theta function.
 We introduce a new way to obtain bounds which is derived from a quadratic 0-1 optimization problem having exactly k variables equal to 1. This allows us to move the m equality constraints into the objective function, leaving a semidefinite program with only 2n equality constraints independent of the number m of edges. Surprisingly, this relaxation is closely related to Schrijver's refinement of the Theta function for the stability number, and to Szegedy's strengthening of the Theta function in the coloring case.
 We propose a further tightening of this bound using the exact subgraph idea in a new way. Rather than looking at subgraphs with a small number of vertices which should be contained in the respective polytope, we now consider subgraphs where the stability number is small (but could have a large number of vertices) and require them to be contained in the corresponding polytope. Computational results on a series of graphs from the literature show the strong potential of this approach.