The maximum $k$-colorable subgraph problem and related problems

Olga Kuryatnikova, Renata Sotirov, J. C. Vera

Research output: Contribution to journalArticleScientificpeer-review


The maximum $k$-colorable subgraph (M$k$CS) problem is to find an induced $k$-colorable subgraph with maximum cardinality in a given graph. This paper is an in-depth analysis of the M$k$CS problem that considers various semidefinite programming relaxations including their theoretical and numerical comparisons. To simplify these relaxations we exploit the symmetry arising from permuting the colors, as well as the symmetry of the given graphs when applicable. We also show how to exploit invariance under permutations of the subsets for other partition problems and how to use the M$k$CS problem to derive bounds on the chromatic number of a graph. Our numerical results verify that the proposed relaxations provide strong bounds for the M$k$CS problem, and that those outperform existing bounds for most of the test instances.
Original languageEnglish
JournalINFORMS Journal on Computing
Publication statusAccepted/In press - Mar 2021


  • k-colorable subgraph problem
  • stable set
  • chromatic number of a graph
  • generalized theta number
  • semidefinite programming
  • Johnsons graphs
  • Hamming graphs


Dive into the research topics of 'The maximum $k$-colorable subgraph problem and related problems'. Together they form a unique fingerprint.

Cite this