The maximum $k$-colorable subgraph problem and related problems
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.
Keywords: $k$-colorable subgraph problem; stable set; chromatic number of a graph; generalized theta number; semidefinite programming; Johnson graphs; Hamming graphs.
Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )
Entry Submitted: 01/27/2020
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|