Generalizations of the tree packing conjecture

DOI10.7151/DMGT.1628MaRDI QIDQ4648788zbMATH OpenOpenAlexWikidataFDO

Authors Dániel Gerbner, Balázs Keszegh, Cory Palmer

Publication date 16 November 2012

Published in Discussiones Mathematicae Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1104.0642

zbMATH Keywords

packingtree packing

Mathematics Subject Classification ID

Trees (05C05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: The Gy'arf'as tree packing conjecture asserts that any set of trees with $2,3,\mathrm{...},k$ vertices has an (edge-disjoint) packing into the complete graph on $k$ vertices. Gy'arf'as and Lehel proved that the conjecture holds in some special cases. We address the problem of packing trees into $k$-chromatic graphs. In particular, we prove that if all but three of the trees are stars then they have a packing into any $k$-chromatic graph. We also consider several other generalizations of the conjecture.

Recommendations

• On the tree packing conjecture
• Packing large trees of consecutive orders
• Packing almost stars into the complete graph
• scientific article; zbMATH DE number 4132205
• scientific article; zbMATH DE number 22649

Cited in

(13)

• Packing a number of copies of a \(( p , q )\)-graph
• Packing branchings under cardinality constraints on their root sets
• An approximate version of the tree packing conjecture
• Packing trees into \(n\)-chromatic graphs
• \(H\)-packing of \(k\)-chromatic graphs
• On cyclic packing of a tree
• scientific article; zbMATH DE number 4132205 (Why is no real title available?)
• scientific article; zbMATH DE number 89770 (Why is no real title available?)
• Seven largest trees pack
• On the tree packing conjecture
• Packing large balanced trees into bipartite graphs
• scientific article; zbMATH DE number 4145943 (Why is no real title available?)
• Problems close to my heart

This page was built for publication: Generalizations of the tree packing conjecture

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4648788)