The complexity for partitioning graphs by monochromatic trees, cycles and paths
Zemin Jin, Xueliang Li · International Journal of Computer Mathematics · 2004
Let G be an edge-coloured graph. We show in this paper that it is NP-hard to find the minimum number of vertex disjoint monochromatic trees which cover the vertices of the graph G. We also show that there is no constant factor approximation algorithm for the problem unless P = NP. The same results hold for the problem of finding the minimum number of vertex disjoint monochromatic cycles (paths, respectively) which cover the vertices of the graph.