Average-degree generalization of the Tree Packing Conjecture

Let T2,,TkT_2,\dots,T_k be trees, where TiT_i has ii vertices, and let GG be a graph on nn vertices.

Average-degree tree-packing conjecture. If GG has average degree at least k1k-1, equivalently at least

k12n\frac{k-1}{2}n

edges, then the set of trees T2,,TkT_2,\dots,T_k has a packing into GG.

This strengthens the minimum-degree version by replacing minimum degree with average degree. The paper proves an analogue for packing only the smaller trees T2,,TsT_2,\dots,T_s when sk/2s\leq k/2, but the full conjecture remains open.

Sources & referencesView supporting material

Primary source

Dániel Gerbner, Balázs Keszegh and Cory Palmer, “Generalizations of the Tree Packing Conjecture”, arXiv:1104.0642 (2011).

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.