The directed Nine Dragon Tree Conjecture for branchings

About 4 years old · traced to

Let DD be a digraph. Write γ(D)\gamma(D) for the fractional arboricity of its underlying graph, and let Δ−(D)\Delta^-(D) and Δ+(D)\Delta^+(D) denote its maximum in-degree and maximum out-degree, respectively. A branching is a spanning subdigraph whose components are arborescences. The directed Nine Dragon Tree Conjecture. For positive integers kk and dd, if

γ(D)≤k+d−kd+1,Δ−(D)≤k+1,\gamma(D) \leq k+\frac{d-k}{d+1},\qquad \Delta^-(D)\leq k+1,

then DD decomposes into k+1k+1 branchings B1,…,Bk,Bk+1B_1,\ldots,B_k,B_{k+1} such that

Δ+(Bk+1)≤d.\Delta^+(B_{k+1})\leq d.

This is proposed as the directed analogue of the Nine Dragon Tree Conjecture. The source gives no resolution, so the conjecture remains open.

References

Primary source

Hui Gao and Daqing Yang, “Digraph analogues for the Nine Dragon Tree Conjecture”, arXiv:2201.10791 (2022).

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.