Hell, Pavol Graph packings. (English) Zbl 1412.05161 Rusu, Irena (ed.), Proceedings of the 6th international conference on graph theory, Marseille-Luminy, France, August 28–September 2, 2000. Amsterdam: Elsevier. Electron. Notes Discrete Math. 5, 170-173 (2000). Summary: A matching of \(G\) can be viewed as a set of disjoint subgraphs of \(G\), each isomorphic to \(K_2\). A natural generalization is a set of disjoint subgraphs each isomorphic to a fixed graph \(H\), or to a member of a fixed family \(\mathcal H\) of graphs. This is a survey of such packing problems. It covers older work of Corneujols, Hartvigsen, and Pulleyblank, of Loebl and Poljak, and of Kirkpatrick and the author, and reports on new results of Kaneko, Kano, Katona, Királyi, Brewster, Pantel, Rizzi, Yeo, Hartvigsen, and the author. The emphasis is on illustrating the use of NP-completeness in ‘predicting’ good characterizations.For the entire collection see [Zbl 0974.00033]. Cited in 10 Documents MSC: 05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) 05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) Keywords:matchings; graph packings; graph factors; Tutte-type theorems PDFBibTeX XMLCite \textit{P. Hell}, Electron. Notes Discrete Math. 5, 170--173 (2000; Zbl 1412.05161) Full Text: Link