DECOMPOSING A GRAPH INTO FORESTS: THE NINE DRAGON TREE CONJECTURE IS TRUE

作者：Jiang, Hongbi; Yang, Daqing^*

来源：Combinatorica, 2017, 37(6): 1125-1137.

DOI：10.1007/s00493-016-3390-1

• decomposition of a graph
• arboricity
• fractional arboricity
• Nash-Williams' Theorem
• Nine Dragon Tree (NDT) Conjecture

The fractional arboricity of a graph G, denoted by I"(f) (G), is defined as . The celebrated Nash-Williams' Theorem states that a graph G can be partitioned into at most k forests if and only if I"(f) (G)aek. The Nine Dragon Tree (NDT) Conjecture [posed by Montassier, Ossona de Mendez, Raspaud, and Zhu, in "Decomposing a graph into forests", J. Combin. Theory Ser. B 102 (2012) 38-52] asserts that if, then G decomposes into k+1 forests with one having maximum degree at most d. In this paper, we prove the Nine Dragon Tree (NDT) Conjecture.

• 出版日期2017-12
• 单位福州大学