Bollobás's consecutive-order tree packing conjecture

Let k1k\geq 1 and let Tn,Tn1,,Tnk+1T_n,T_{n-1},\dots,T_{n-k+1} be trees, where TnjT_{n-j} has njn-j vertices. The trees pack into KnK_n when they can be found as pairwise edge-disjoint subgraphs of the complete graph KnK_n. Bollobás's conjecture. For every k1k\geq 1 there is an n0(k)n_0(k) such that if n>n0(k)n>n_0(k), then any set of kk trees Tn,Tn1,,Tnk+1T_n,T_{n-1},\dots,T_{n-k+1} such that TnjT_{n-j} has njn-j vertices pack into KnK_n. This weakens Gyárfás's Tree Packing Conjecture, which asks for packing trees of every order from 11 through nn; the paper confirms the conjecture for certain trees and, as a consequence, for k5k\leq 5.

Sources & referencesView supporting material

Primary source

Andrzej Żak, “Packing large trees of consecutive orders”, arXiv:1510.07467 (2015).

Additional references

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

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.