Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
8903846 | Journal of Combinatorial Theory, Series B | 2018 | 15 Pages |
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.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Daqing Yang,