Efficient Approximation of Convex Recolorings

Shlomo Moran, Sagi Snir

A coloring of a tree is convex if the vertices that pertain to any color induce a connected subtree; a partial coloring (which assigns colors to some of the vertices) is convex if…