Improved semidefinite programming bounds for the maximum $k$-colorable subgraph problem

Mathijs Barkel, Renata Sotirov

We study the maximum $k$-colorable subgraph (M$k$CS) problem, which consists in finding a largest $k$-colorable induced subgraph in a given graph. We consider a Semidefinite Progra…