{"id":"arxiv/2605.02456","url":"https://arxiv.org/abs/2605.02456","tags":["math.OC"],"score":0,"title":"Improved semidefinite programming bounds for the maximum $k$-colorable subgraph problem","domain":"math.OC","source":"arxiv","authors":["Mathijs Barkel","Renata Sotirov"],"reviews":0,"subject":"math.OC","summary":"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 Programming (SDP) relaxation for the M$k$CS problem and regard its resulting upper bound as a graph parameter. We present several properties of this graph parameter, from which we obtain that the M$k$CS problem is solvable in polynomial time for $k$-perfect graphs. We further derive two novel families of valid inequalities to strengthen the SDP relaxation. The first family reduces to a family of inequalities for the…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-05-04","reactions":{}}