The tree packing conjecture for trees of almost linear maximum degree

arXiv2106.11720MaRDI QIDQ6370947FDOQ6370947

Authors: Peter Allen, Julia Böttcher, Dennis Clemens, Jan Hladký, Diana Piguet, Anusch Taraz 

Publication date: 22 June 2021

Abstract: We prove that there is $c>0$ such that for all sufficiently large $n$, if $T_1,dots,T_n$ are any trees such that $T_i$ has $i$ vertices and maximum degree at most $cn/logn$, then $T_1,dots,T_n$ packs into $K_n$. Our main result actually allows to replace the host graph $K_n$ by an arbitrary quasirandom graph, and to generalize from trees to graphs of bounded degeneracy that are rich in bare paths, contain some odd degree vertices, and only satisfy much less stringent restrictions on their number of vertices.

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

This page was built for publication: The tree packing conjecture for trees of almost linear maximum degree

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