The complexity for partitioning graphs by monochromatic trees, cycles and paths.

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. [ABSTRACT FROM AUTHOR]