Packing problems in edge-colored graphs (Q1331890)

Let \(F\) be a graph edge-colored with \(k\) colors. A partition (family of disjoint subsets, respectively) \(\{V_ 1,\dots,V_ m\}\) of the vertex set of a complete graph edge-colored with \(k\) colors is an \(F\)-partition (\(F\)-packing, respectively) if each \(V_ i\) contains a spanning copy of \(F\) (with the same color pattern as \(F\)). It is shown in the paper that the problem of existence of an \(F\)-partition is NP-complete unless \(F\) consists of isolated vertices and edges, or \(k=2\) and \(F\) is properly 2- edge-colored. It is noted that the case when \(F\) is an isolated edge is a familiar matching problem and, hence, in this case, the problem is in P. Necessary and sufficient conditions for the existence of an \(F\)-packing are also given for \(F\) being a properly colored path of length 2. Moreover, a polynomial time algorithm is described to test them. Similar results are proved for \(F\) consisting of two isolated and differently colored edges. Packings are considered in a more general setting where, instead of one graph \(F\), we have a family \(\mathcal F\) of \(k\)-edge-colored graphs. Specifically, sufficient conditions are provided that guarantee existence of large packings of (some) families of trees and forests.