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 (In m + 1) -approximation for the problem of finding the minimum number of monochromatic cliques partitioning V(G) for a K-4(-) -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 NP subset of DTIME(N-O(log log N)), for any is an element of >= 0 there is no approximation algorithm for finding the minimum number of multicolored trees partitioning V(G) with performance 50/521 (1 - is an element of) ln vertical bar V vertical bar. (c) 2007 Elsevier B.V. All rights reserved.
monochromatic multicolored partition complexity inapproximability