An Approximate Version of the Strong Nine Dragon Tree Conjecture

The Strong Nine Dragon Tree Conjecture asserts that for any integers $k$ and $d$ any graph with fractional arboricity at most $k + \frac{d}{d+k+1}$ decomposes into $k+1$ forests, such that for at least one of the forests, every connected component contains at most $d$ edges. We prove this conjecture when $d \leq k+1$. We also prove an approximate version of this conjecture, that is, we prove that for any positive integers $k$ and $d$, any graph with fractional arboricity at most $k + \frac{d}{d+k+1}$ decomposes into $k+1$ forests, such that one for at least one of the forests, every connected component contains at most $d + \frac{d(k (2\lceil \frac{d}{k+1} +2 \rceil)^{\lceil \frac{d}{k+1} + 2) \rceil} - k)}{k+1}$ edges.

No reviews yet.

No comments yet.