##
**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.

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 |

### 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 |

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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.