The minimum chromatic violation problem: a polyhedral approach

ESCALANTE, MARIANA SILVINA; UGARTE, MARIA ELISA; VARALDO, MARIA DEL CARMEN

Santiago de Chile

Congreso; Latin-Iberoamerican Conference on Operations Research (CLAIO 2016); 2016

ALIO-IFORS

In this contribution we analyze the problem of nding a vertex coloring of a graph with theadditional property that there are a xed set of edges whose endpoint can have the same color.We say that these edges can be violated with respect to the usual property of coloring in a graph.We present an integer programming formulation of this problem and begin with the study ofthe convex hull of integer solutions in it. These formulation involves the standard constraintsfor coloring in a graph and therefore we are forced to study this polytope for the families ofgraphs herein considered. We obtain the dimension, the minimum inequality system and someexponentially sized group of valid inequalities that we strongly believe suce to describe thechromatic violation polytope for small instances of complete graphs with one violable edge