The minimum chromatic violation problem: a polyhedral study

BRAGA, MONICA; DELLE DONNE, DIEGO; ESCALANTE, MARIANA SILVINA; MARENCO, JAVIER; UGARTE, MARIA ELISA; VARALDO, MARIA DEL CARMEN

Marsella

Simposio; LAGOS 2017- IX Latin American Algorithms, Graphs and Optimization Symposium; 2017

We propose a generalization of the k-coloring problem, namely the minimum chro-matic violation problem (MCVP). Given a graph G = (V;E), a set of weak edgesF E and a set of colors C, the MCVP asks for a jCj-coloring of the graphG0 = (V;E n F) minimizing the number of weak edges with both endpoints re-ceiving the same color. We present an integer programming formulation for thisproblem and provide an initial polyhedral study of the polytopes arising from thisformulation. We give partial characterizations of facet-inducing inequalities andwe show how facets from weaker and stronger instances of MCVP (i.e., more/lessweak edges) are related. We then introduce a general lifting procedure which gen-erates (sometimes facet-inducing) valid inequalities from generic valid inequalitiesand we present several facet-inducing families arising from this procedure. Finally,we present another family of facet-inducing inequalities which is not obtained fromthe prior lifting procedure.