Strong Nine Dragon Tree Conjecture

Let GG be a graph, and let dd and kk be positive integers. Define the fractional arboricity of GG by

γ(G)=maxHG,v(H)2e(H)v(H)1.\gamma(G)=\max_{H\subseteq G,\,v(H)\geq 2}\frac{e(H)}{v(H)-1}.

Strong Nine Dragon Tree Conjecture. If

γ(G)k+dd+k+1,\gamma(G)\leq k+\frac{d}{d+k+1},

then there is a partition of GG into k+1k+1 forests such that, in one forest, every connected component has at most dd edges.

The conjecture strengthens the Nine Dragon Tree Theorem, which requires only that one forest have maximum degree dd. It is known when dk+1d\leq k+1 and when d2(k+1)d\leq 2(k+1); all other cases remain open.

Sources & referencesView supporting material

Primary source

Sebastian Mies and Benjamin Moore, “An Approximate Version of the Strong Nine Dragon Tree Conjecture”, arXiv:2406.05022 (2024).

Additional references

6 papers in this index state this conjecture (2019–2024). The statement above is taken from the most recent of them; the others are arXiv:2310.00931, arXiv:2208.06336, arXiv:2201.10791, arXiv:1905.02600, arXiv:1904.12435.

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.