The convex recoloring problem: polyhedra, facets and computational experiments (Q263202)

This article considers the convex recoloring problem on graphs. Given a graph, a convex coloring of vertices is defined as one where the set of vertices having the same color is connected. The authors study the problem of converting any graph coloring into a convex coloring by modifying the color of the minimum number of vertices. The paper begins with an introduction to graph coloring and the background definitions in this area, followed by a novel integer programming formulation of the convex recoloring problem. Then the authors proceed to study the convex polytope defined by the feasible integer solutions of the integer program and derive, with proof, by facet-defining inequalities for this polyhedron. The third section concentrates on the facets that correspond to trees where further facet-defining inequalities are produced. In order to use these inequalities in a branch-and-cut framework, a polynomial-time separation algorithm to generate these inequalities from any fractional relaxation solution is described. The last section of this very interesting article contains the results of extensive computational experimentation evaluating the proposed algorithm.