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 . The stronger version of the conjecture, described below, is still open.

Remarks

This conjecture was proposed by Montassier et al., 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 . 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 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 : 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 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 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. 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].