Gyárfás–Lehel Tree Packing Conjecture

From papers

Let $T_1,\dotsc,T_n$ be trees, and let $v(T_i)$ denote the number of vertices of $T_i$ . A collection of graphs packs into a graph $G$ if there are edge-disjoint subgraphs of $G$ isomorphic to the graphs in the collection. Tree Packing Conjecture. Any collection $T_1,\dotsc,T_n$ of trees with

v(T_i)=i

for each $i$ packs into the complete graph $K_n$ . This conjecture concerns packing trees of all sizes into a graph whose order matches the largest tree; its relationship with Ringel's related tree-packing conjecture makes it a central problem in graph decomposition.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Equivalent formulations 1

Other statements of this same problem, merged from separate entries. Each is equivalent to the statement above — proving any one settles them all.

Gyárfás–Lehel tree packing conjecture
Let $n\in\mathbb N$ and let $T_1,\ldots,T_n$ be trees with $|T_i|=i$ . A decomposition of a graph into these trees is a collection of pairwise edge-disjoint copies covering every edge. Gyárfás–Lehel's conjecture. The complete graph $K_n$ has a decomposition into copies of $T_1,\ldots,T_n$ . This conjecture motivates optimal packing and decomposition results for families of trees; the paper proves it for families satisfying suitable bounded-degree conditions, but the unrestricted statement remains open.
source: Felix Joos, Jaehoon Kim, Daniela Kühn and Deryk Osthus, “Optimal packings of bounded degree trees”, arXiv:1606.03953 (2019).

Sources & referencesView supporting material

Primary source

Asaf Ferber and Wojciech Samotij, “Packing trees of unbounded degrees in random graphs”, arXiv:1607.07342 (2016).

Additional references

2 papers in this index state this conjecture (2015–2016). The statement above is taken from the most recent of them; the others are arXiv:1512.08701.

1 week ago

Progress summary

Equivalent formulations 1

Gyárfás–Lehel tree packing conjecture

Primary source

Additional references