The maximum k-colorable subgraph problem and related problems

DOI10.1287/IJOC.2021.1086MaRDI QIDQ6333536arXivFDO

Authors Olga Kuryatnikova, Renata Sotirov, Juan Vera

Publication date 27 January 2020

Published in arXiv

Full work available at URL https://doi.org/10.1287/IJOC.2021.1086

Mathematics Subject Classification ID

Operations research, mathematical programming (90-XX)

arXiv classification

math.OC

Abstract: 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.

This page was built for publication: The maximum $k$-colorable subgraph problem and related problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6333536)