pith. sign in

arxiv: 1502.04755 · v1 · pith:LZMKSKKEnew · submitted 2015-02-17 · 🧮 math.CO

Decomposition of Sparse Graphs into Forests: The Nine Dragon Tree Conjecture for k le 2

classification 🧮 math.CO
keywords conjecturearboricitydragonforestsfracmaximumninetree
0
0 comments X
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.