The minimum chromatic violation problem: a polyhedral study

We propose a generalization of the k-coloring problem, namely the minimum chromatic 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 |C|-coloring of the graph G′=(V,E\F) minimizing the number of weak edges with both endpoints receiving the same color. We present an integer programming formulation for this problem and provide an initial polyhedral study of the polytopes arising from this formulation. We give partial characterizations of facet-inducing inequalities and we show how facets from weaker and stronger instances of MCVP (i.e., more/less weak edges) are related. We then introduce a general lifting procedure which generates (sometimes facet-inducing) valid inequalities from generic valid inequalities and we present several facet-inducing families arising from this procedure. Finally, we present another family of facet-inducing inequalities which is not obtained from the prior lifting procedure.