Optimal packings of bounded degree trees

Felix Joos, Jaehoon Kim, Daniela Kuhn, Deryk Osthus

Research output: Contribution to journalArticlepeer-review

10 Citations (Scopus)
708 Downloads (Pure)

Abstract

We prove that if T1,…,Tn is a sequence of bounded degree trees such that Ti has i vertices, then Kn has a decomposition into T1,…,Tn. This shows that the tree packing conjecture of Gyárfás and Lehel from 1976 holds for all bounded degree trees (in fact, we can allow the first o(n) trees to have arbitrary degrees). Similarly, we show that Ringel's conjecture from 1963 holds for all bounded degree trees. We deduce these results from a more general theorem, which yields decompositions of dense quasi-random graphs into suitable families of bounded degree graphs. Our proofs involve Szemerédi's regularity lemma, results on Hamilton decompositions of robust expanders, random walks, iterative absorption as well as a recent blow-up lemma for approximate decompositions.
Original languageEnglish
Pages (from-to)3573-3647
Number of pages74
JournalJournal of the European Mathematical Society
Volume21
Issue number12
DOIs
Publication statusPublished - 5 Aug 2019

Keywords

  • Graph decompositions
  • Packings
  • Quasirandomness
  • Trees

ASJC Scopus subject areas

  • Mathematics(all)
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Optimal packings of bounded degree trees'. Together they form a unique fingerprint.

Cite this