Convex Recoloring of General Graphs: Formulations, Polyhedra, and Computational Experiments

Boyue Lin, Phablo F. S. Moura, Roel Leus

A vertex coloring of a graph is convex if the vertices of each color induce a connected subgraph. In the convex recoloring problem (CR), the goal is to find a convex coloring while…