Packing problems in edge-colored graphs. (English) Zbl 0806.05054

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.


05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C15 Coloring of graphs and hypergraphs
Full Text: DOI


[2] Benkouar, A.; Manoussakis, Y.; Paschos, V.; Saad, R., On the complexity of finding alternating hamiltonian and Eulerian cycles in edge-colored complete graphs, (Lecture Notes in Computer Science, 557 (1991), Springer: Springer Berlin), 190-198
[3] Caro, Y.; Tuza, Zs., Decompositions of partially ordered sets into chains and antichains of given size, Order, 5, 3, 245-255 (1988) · Zbl 0665.06002
[4] Even, S.; Kariv, O., An \(O(n^{2.5})\) algorithm for maximum matchings in general graphs, (Proceedings of the 16th Annual Symposium on Foundations of Computer Science, Berkeley, 1975 (1975), IEEE Computer Society Press: IEEE Computer Society Press New York), 100-112
[5] Garey, M.; Johnson, D., Computers and Intractability — A Guide to the Theory of NP-Completeness (1979), Freeman: Freeman New York · Zbl 0411.68039
[6] Kirkpatrick, D.; Hell, P., On the complexity of general graph factor problems, SIAM J. Comput., 12, 601-609 (1983) · Zbl 0525.68023
[7] Lonc, Z.; Truszczynski, M., Decompositions of large uniform hypergraphs, Order, 1, 345-350 (1985) · Zbl 0558.05048
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.