Packing problems in edge-colored graphs.

*(English)*Zbl 0806.05054Let \(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 |

PDF
BibTeX
XML
Cite

\textit{P. Hell} et al., Discrete Appl. Math. 52, No. 3, 295--306 (1994; Zbl 0806.05054)

Full Text:
DOI

**OpenURL**

##### References:

[1] | 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, (), 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(n2.5) algorithm for maximum matchings in general graphs, (), 100-112 |

[5] | Garey, M.; Johnson, D., Computers and intractability — A guide to the theory of NP-completeness, (1979), 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. · 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.