# Decomposition into forests and a bounded-degree subgraph

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

[math]\left\lceil\frac{(k+1)\epsilon}{1-\epsilon}\right\rceil[/math] ?

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
[math]\left\lceil\frac{(k+1)\epsilon}{1-\epsilon}\right\rceil .[/math]

**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 [math]\left\lceil\frac{k\epsilon+1}{1-\epsilon}\right\rceil .[/math]

## Partial Results

Currently the best known results are the following:

- It is shown in
^{[3]}that the Nine Dragon Tree conjecture holds if [math]\epsilon=1/2[/math], and the weaker conjecture holds if [math]\epsilon \geq 1/2[/math]. - Stronger results are proved about the
*k=1*case in^{[3]}: the strong conjecture is true if [math]\epsilon \leq 1/2[/math], and the NDT conjecture is true if [math]\epsilon \leq 3/4[/math]. - Király and Lau
^{[4]}showed that the weak conjecture holds if we relax the degree bound to [math]\left\lceil\frac{k\epsilon+1}{1-\epsilon}\right\rceil .[/math] - Chen, Kim, Kostochka, West, and Zhu
^{[5]}proved the NDT conjecture for [math]k \leq 2[/math] (the [math]\epsilon \leq 1/4[/math] 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 [math]2(k+\epsilon)[/math], then*G*can be decomposed into*k+1*pseudoforests, one of which has maximum degree at most [math]\left\lceil\frac{(k+1)\epsilon}{1-\epsilon}\right\rceil[/math].

## References

- ↑ H. Jiang, D. Yang,
*Decomposing a graph into forests: The nine dragon tree conjecture is true*, Combinatorica, available online (2016), DOI link - ↑ 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.0}^{3.1}^{3.2}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 - ↑ T. Király, L.C. Lau,
*Degree bounded forest covering*, LNCS 6655 (2011), 315-323, DOI link, EGRES link - ↑ M. Chen, S.-J. Kim, A. Kostochka, D.B. West, X. Zhu,
*Decomposition of Sparse Graphs into Forests: The Nine Dragon Tree Conjecture for [math]k \leq 2[/math]*, arXiv link, author link - ↑ G. Fan, Y. Li, N. Song, D. Yang,
*Decomposing a graph into pseudoforests with one having bounded degree*, DOI link