On the minimum monochromatic or multicolored subgraph partition problems

Let G=(V,E) be an edge-colored graph. A subgraph H is said to be monochromatic if all the edges of H have the same color, and multicolored if no two edges of H have the same color. We investigate the complexity of the problems for finding the minimum number of monochromatic or multicolored subgraphs, such as cliques, cycles, trees and paths, partitioning V(G), depending on the number of colors used and the maximal number of times a color appears in a coloring. We also present a greedy scheme that yields a (lnm+1)-approximation for the problem of finding the minimum number of monochromatic cliques partitioning V(G) for a -free graph G, where m is the size of the largest monochromatic clique in G. By a slightly modification of the approximation algorithm, it can be used for the multicolored case. We show that unless , for any ϵ≥0 there is no approximation algorithm for finding the minimum number of multicolored trees partitioning V(G) with performance 50/521(1−ϵ)ln|V|.