Packing large trees of consecutive orders

DOI10.1016/J.DISC.2016.07.022MaRDI QIDQ2374181zbMATH OpenOpenAlexFDO

Authors Andrzej Żak

Publication date 14 December 2016

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

packing of graphstree packing conjecturetrees

Mathematics Subject Classification ID

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

Abstract: A conjecture by Bollob'as from 1995 (which is a weakenning of the famous Tree Packing Conjecture by Gy'arf'as from 1976) states that any set of $k$ trees $T_n,T_{n-1},dots,T_{n-k+1}$, such that $T_{n-i}$ has $n-i$ vertices, pack into $K_n$, provided $n$ is sufficiently large. We confirm Bollob'as conjecture for trees $T_n,T_{n-1},dots,T_{n-k+1}$, such that $T_{n-i}$ has $k-1-i$ leaves or a pending path of order $k-1-i$. As a consequence we obtain that the conjecture is true for $kleq5$.

Recommendations

• On the tree packing conjecture
• scientific article; zbMATH DE number 22649
• Packing almost stars into the complete graph
• scientific article; zbMATH DE number 4145943
• Packing trees of bounded diameter into the complete graph

Cites work

• An approximate version of the tree packing conjecture
• An extremal result for subgraphs with few edges
• scientific article; zbMATH DE number 3604921 (Why is no real title available?)
• scientific article; zbMATH DE number 3623611 (Why is no real title available?)
• scientific article; zbMATH DE number 1022391 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 830463 (Why is no real title available?)
• On the tree packing conjecture
• Packing trees in complete graphs
• The Turán number of sparse spanning graphs

Cited in

(10)

• Packing a number of copies of a \(( p , q )\)-graph
• Optimal packings of bounded degree trees
• Packing spanning graphs from separable families
• Efficient Chaining of Seeds in Ordered Trees
• A blow-up lemma for approximate decompositions
• Generalizations of the tree packing conjecture
• Packing trees into complete \(k\)-partite graph
• On the tree packing conjecture
• Placing two edge-disjoint copies of a tree into a bipartite graph
• Seven largest trees pack

This page was built for publication: Packing large trees of consecutive orders

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