Gyárfás–Lehel Tree Packing Conjecture

About 11 years old · traced to 2015

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.

Equivalent formulations 1Other wordings

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).

References

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.

Posted 1 month ago

Gyárfás–Lehel Tree Packing Conjecture

Gyárfás–Lehel tree packing conjecture

Primary source

Additional references

Progress summary

Solutions 0