Strengthening of the semidefinite relaxation for graph coloring probl...

Let G = (V, E) be a graph with |V| = n. The chromatic number χ(G) is the smallest t such that vertices of G can be partitioned into t stable sets. Let S = (s₁, …, s_k) be a matrix where each column s_i represents a stable set vector and where the corresponding stable sets partition vertices into k sets. The n × n matrix X = SS^T is called coloring matrix. Now let I ⊆ V be a subset of vertices of G. We denote by G_I the subgraph that is induced by the set of vertices I, and by X_I = (X_i,j) _i,j ∈I the submatrix of X which is indexed by I. In our work we consider subgraphs G_I with I = {1, …, k + 1} such that vertices {1, …, k} form a clique C, and vertex k + 1 is not adjacent to all vertices in C, and we show that the inequality Σ _i∈C X_i,k+1 ≤ 1 holds for any coloring matrix X_I . Furthermore, we introduce respective inequalities into the semidefinite relaxation and show that the Lovász theta number can be strengthened. Finally, we compare our bounds with relaxations given by Szegedy and Meurdesoif and present computational results.