On the tree packing conjecture

József Balogh, Cory Palmer

Research output: Contribution to journalArticlepeer-review

Abstract

The Gyárfás tree packing conjecture states that any set of n-1 trees T1, T2, Tn-1 such that Ti has n-i+1 vertices packs into Kn (for n large enough). We show that t = 1 10n1/4 trees T1, T2,Tt such that Ti has n-i+1 vertices packs into Kn+1 (for n large enough). We also prove that any set of t = 1 10n1/4 trees T1, T2, Tt such that no tree is a star and Ti has n-i+1 vertices packs into Kn (for n large enough). Finally, we prove that t = 1 4n1/3 trees T1, T2, Tt such that Ti has n - i + 1 vertices packs into Kn as long as each tree has maximum degree at least 2n2/3 (for n large enough). One of the main tools used in the paper is the famous spanning tree embedding theorem of Komlós, Sárközy, and Szemerédi [Combin. Probab. Comput., 10 (2001), pp. 397-416].

Original languageEnglish (US)
Pages (from-to)1995-2006
Number of pages12
JournalSIAM Journal on Discrete Mathematics
Volume27
Issue number4
DOIs
StatePublished - Dec 1 2013

Keywords

  • Packing
  • Tree
  • Tree packing

ASJC Scopus subject areas

  • Mathematics(all)

Fingerprint

Dive into the research topics of 'On the tree packing conjecture'. Together they form a unique fingerprint.

Cite this