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

Hell, P.; Manoussakis, Y.; Tuza, Zs.

Discrete Appl. Math. 52, No. 3, 295-306 (1994).

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.

Reviewer: M.Truszczyński (Lexington)

MSC:

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

Keywords:

partition; packing; colored graphs; matching; polynomial time algorithm

References:

[1]	B. Bauslaugh, personal communication, Simon Fraser University (1991).; B. Bauslaugh, personal communication, Simon Fraser University (1991).
[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
[8]	Y. Manoussakis, Alternating paths in edge-colored complete graphs, Discrete Appl. Math., to appear.; Y. Manoussakis, Alternating paths in edge-colored complete graphs, Discrete Appl. Math., to appear. · Zbl 0819.05039