The Nine Dragon Tree Conjecture for bounded forest decompositions

About 10 years old · traced to

Let GG be a graph, and let k,dk,d be nonnegative integers. The Nine Dragon Tree Conjecture. If

γf(G)≤k+dd+k+1,\gamma_f(G)\leq k+\frac{d}{d+k+1},

then GG decomposes into k+1k+1 forests, one of which is dd-bounded. The conjecture is the graph-theoretic Nine Dragon Tree statement concerning decomposition into forests with one bounded component. It was proved by Jiang and Yang, so the conjecture is resolved.

References

Primary source

Hui Gao, “Packing spanning arborescences with extra large one”, arXiv:2511.18952 (2025).

Additional references

3 papers in this index state this conjecture (2016–2025). The statement above is taken from the most recent of them; the others are arXiv:2201.10791, arXiv:1608.05352.

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.