Semidefinite relaxations for stable set and coloring

Stable set and coloring problems are fundamental combinatorial optimization problems. A standard method in combinatorial optimization is to write a problem as a linear problem with integer variables, and then to consider its relaxation in order to get bounds on the optimal solution. This research focuses on bounds which are obtained by semidefinite relaxations using semidefinite programming. A famous semidefinite relaxation for both stable set and coloring problems is the Lovász theta function. We introduce a new way to obtain bounds which are derived from quadratic 0-1 optimization problems which can be used for getting bounds on the stability and chromatic numbers of the graph. Furthermore, we propose a further tightening of this bound using the exact subgraph idea in a new way. We present initial results and discuss open issues.