Optimization Online


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

Olga Kuryatnikova(okuryatnikova***at***ivey.ca)
Renata Sotirov(r.sotirov***at***uvt.nl)
Juan Vera(j.c.veralizcano***at***uvt.nl)

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 )


Download: [PDF]

Entry Submitted: 01/27/2020
Entry Accepted: 01/27/2020
Entry Last Modified: 01/27/2020

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society