Decomposition of Sparse Graphs into Forests: The Nine Dragon Tree Conjecture for k le 2
classification
🧮 math.CO
keywords
conjecturearboricitydragonforestsfracmaximumninetree
read the original abstract
For a loopless multigraph $G$, the fractional arboricity $Arb(G)$ is the maximum of $\frac{|E(H)|}{|V(H)|-1}$ over all subgraphs $H$ with at least two vertices. Generalizing the Nash-Williams Arboricity Theorem, the Nine Dragon Tree Conjecture asserts that if $Arb(G)\le k+\frac{d}{k+d+1}$, then $G$ decomposes into $k+1$ forests with one having maximum degree at most $d$. The conjecture was previously proved for $d=k+1$ and for $k=1$ when $d \le 6$. We prove it for all $d$ when $k \le 2$, except for $(k,d)=(2,1)$.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.