The tree packing conjecture for trees of almost linear maximum degree

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

Publication date 22 June 2021

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

Abstract: We prove that there is

c > 0

such that for all sufficiently large

n

, if

T_{1}, d o t s, T_{n}

are any trees such that

T_{i}

has

i

vertices and maximum degree at most

c n / l o g n

, then

T_{1}, d o t s, 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.

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)