The Strong Nine Dragon Tree Conjecture is true for $d\le k+1$

Abstract

The arboricity $\Gamma (G)$ of an undirected graph $G=(V,E)$ is the minimal number such that $E$ can be partitioned into $\Gamma (G)$ forests. Nash-Williams' formula states that $k=\lceil \gamma (G)\rceil$, where $\gamma (G)$ is the maximum of $|E_H|/(|V_H|-1)$ over all subgraphs $(V_H,E_H)$ of $G$ with $|V_H|\ge 2$. The Strong Nine Dragon Tree Conjecture states that if $\gamma (G)\le k+\frac{d}{d+k+1}$ for $k,d\in {\mathbb{N}}_0$, then there is a partition of the edge set of $G$ into $k+1$ forests such that one forest has at most $d$ edges in each connected component. We settle the conjecture for $d\le k+1$. For $d\le 2(k+1)$, we cannot prove the conjecture, however we show that there exists a partition in which the connected components in one forest have at most $d+\lceil k\cdot \frac{d}{k+1}\rceil -k$ edges. As an application of this theorem, we show that every $5$-edge-connected planar graph $G$ has a $\frac{5}{6}$-thin spanning tree. This theorem is best possible, in the sense that we cannot replace $5$-edge-connected with $4$-edge-connected, even if we replace $\frac{5}{6}$ with any positive real number less than $1$. This strengthens a result of Merker and Postle which showed $6$-edge-connected planar graphs have a $\frac{18}{19}$-thin spanning tree.

22 pages, v2: paper updated in accordance to referee comments. v3: Arguments simplified, updated to shorten proof