The directed Nine Dragon Tree Conjecture for branchings

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+dkd+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.

Sources & referencesView supporting material

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.