Article ID Journal Published Year Pages File Type
8903846 Journal of Combinatorial Theory, Series B 2018 15 Pages PDF
Abstract
The fractional arboricity of a graph G, denoted by γf(G), is defined as γf(G)=maxH⊆G,v(H)>1⁡e(H)v(H)−1. The famous Nash-Williams' Theorem states that a graph G can be partitioned into at most k forests if and only if γf(G)≤k. A graph is d-bounded if it has maximum degree at most d. The Nine Dragon Tree (NDT) Conjecture [posed by Montassier, Ossona de Mendez, Raspaud, and Zhu, at [11]] asserts that if γf(G)≤k+dk+d+1, then G decomposes into k+1 forests with one being d-bounded. In this paper, it is proven that the Nine Dragon Tree Conjecture is true for all the cases in which d=1.
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,