# Decomposition into forests and a bounded-degree subgraph

Is it true that if the arboricity of a graph G is at most $k+\epsilon$ for some positive integer k and $0\lt\epsilon\lt1$, then G can be decomposed into k+1 forests, one of which has maximum degree at most

$\left\lceil\frac{(k+1)\epsilon}{1-\epsilon}\right\rceil$ ?

The conjecture was proved by Hongbi Jiang and Daqing Yang [1]. The stronger version of the conjecture, described below, is still open.

## Remarks

This conjecture was proposed by Montassier et al.[2], who named it the Nine Dragon Tree (NDT) Conjecture. There is a weaker and a stronger version of the conjecure that might be interesting to study.

Weak conjecture. For the same arboricity bound, G can be decomposed into k forests and a subgraph of maximum degree at most $\left\lceil\frac{(k+1)\epsilon}{1-\epsilon}\right\rceil .$

Strong conjecture [3]. For the same arboricity bound, G can be decomposed into k+1 forests, one of which has components of size at most $\left\lceil\frac{k\epsilon+1}{1-\epsilon}\right\rceil .$

## Partial Results

Currently the best known results are the following:

• It is shown in [3] that the Nine Dragon Tree conjecture holds if $\epsilon=1/2$, and the weaker conjecture holds if $\epsilon \geq 1/2$.
• Stronger results are proved about the k=1 case in [3]: the strong conjecture is true if $\epsilon \leq 1/2$, and the NDT conjecture is true if $\epsilon \leq 3/4$.
• Király and Lau [4] showed that the weak conjecture holds if we relax the degree bound to $\left\lceil\frac{k\epsilon+1}{1-\epsilon}\right\rceil .$
• Chen, Kim, Kostochka, West, and Zhu [5] proved the NDT conjecture for $k \leq 2$ (the $\epsilon \leq 1/4$ case is proved in a manuscript of Yang).
• A related result hase been proven by Fan et al. [6] about pseudoforests, i.e. subgraphs having at most one cycle in each component. They showed that if the maximum average degree of a graph G is $2(k+\epsilon)$, then G can be decomposed into k+1 pseudoforests, one of which has maximum degree at most $\left\lceil\frac{(k+1)\epsilon}{1-\epsilon}\right\rceil$.

## References

1. H. Jiang, D. Yang, Decomposing a graph into forests: The nine dragon tree conjecture is true, Combinatorica, available online (2016), DOI link
2. M. Montassier, P. Ossona de Mendez, A. Raspaud, X. Zhu, Decomposing a graph into forests, Journal of Combinatorial Theory B 102 (2012) 38–52, DOI link
3. S.J. Kim, A.V. Kostochka, D.B. West, H. Wu, X. Zhu, Decomposition of sparse graphs into forests and a graph with bounded degree, Journal of Graph Theory, DOI link, Author link
4. T. Király, L.C. Lau, Degree bounded forest covering, LNCS 6655 (2011), 315-323, DOI link, EGRES link
5. M. Chen, S.-J. Kim, A. Kostochka, D.B. West, X. Zhu, Decomposition of Sparse Graphs into Forests: The Nine Dragon Tree Conjecture for $k \leq 2$, arXiv link, author link
6. G. Fan, Y. Li, N. Song, D. Yang, Decomposing a graph into pseudoforests with one having bounded degree, DOI link