The complexity of minimum convex coloring

A coloring of the vertices of a graph is called convex if each subgraph induced by all vertices of the same color is connected. We consider three variants of recoloring a colored graph with minimal cost such that the resulting coloring is convex. Two variants of the problem are shown to be NPNP-hard on trees even if in the initial coloring each color is used to color only a bounded number of vertices. For graphs of bounded treewidth, we present a polynomial-time (2+ϵ)(2+ϵ)-approximation algorithm for these two variants and a polynomial-time algorithm for the third variant. Our results also show that, unless NP⊆DTIME(nO(loglogn))NP⊆DTIME(nO(loglogn)), there is no polynomial-time approximation algorithm with a ratio of size (1−o(1))lnlnN(1−o(1))lnlnN for the following problem: given pairs of vertices in an undirected NN-vertex graph of bounded treewidth, determine the minimal possible number ll for which all except ll pairs can be connected by disjoint paths.