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

Abstract

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.

Keywords:

• Combinatorial problems
• Computational complexity
• Vertex disjoint
• Tree, cycle and path
• Monochromatic

Acknowledgements

This Research was supported by NSFC.