zbMATH — the first resource for mathematics

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.

MSC:
 05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) 05C15 Coloring of graphs and hypergraphs
Full Text:
References:
  B. Bauslaugh, personal communication, Simon Fraser University (1991).  Benkouar, A.; Manoussakis, Y.; Paschos, V.; Saad, R., On the complexity of finding alternating Hamiltonian and Eulerian cycles in edge-colored complete graphs, (), 190-198  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  Even, S.; Kariv, O., An O(n2.5) algorithm for maximum matchings in general graphs, (), 100-112  Garey, M.; Johnson, D., Computers and intractability — A guide to the theory of NP-completeness, (1979), Freeman New York · Zbl 0411.68039  Kirkpatrick, D.; Hell, P., On the complexity of general graph factor problems, SIAM J. comput., 12, 601-609, (1983) · Zbl 0525.68023  Lonc, Z.; Truszczynski, M., Decompositions of large uniform hypergraphs, Order, 1, 345-350, (1985) · Zbl 0558.05048  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. 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.