New bounds for the max-$k$-cut and chromatic number of a graph

Edwin R. van Dam, Renata Sotirov

We consider several semidefinite programming relaxations for the max-$k$-cut problem, with increasing complexity. The optimal solution of the weakest presented semidefinite program…