Name
Title | ||
|---|---|---|
Decomposition of sparse graphs into forests: The Nine Dragon Tree Conjecture for k ≤ 2. |
Abstract | ||
|---|---|---|
For a loopless multigraph G, the fractional arboricity Arb(G) is the maximum of |E(H)||V(H)|−1 over all subgraphs H with at least two vertices. Generalizing the Nash-Williams Arboricity Theorem, the Nine Dragon Tree Conjecture asserts that if Arb(G)≤k+dk+d+1, then G decomposes into k+1 forests with one having maximum degree at most d. The conjecture was previously proved for d=k+1 and for k=1 when d≤6. We prove it for all d when k≤2, except for (k,d)=(2,1). |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1016/j.jctb.2016.09.004 | Journal of Combinatorial Theory, Series B |
Keywords | DocType | Volume |
Nine Dragon Tree Conjecture,Arboricity,Nash-Williams Arboricity Formula,Fractional arboricity,Forest,Graph decomposition,Discharging method,Sparse graph | Journal | 122 |
ISSN | Citations | PageRank |
0095-8956 | 0 | 0.34 |
References | Authors | |
0 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Min Chen | 1 | 5 | 1.22 |
| Seog-Jin Kim | 2 | 151 | 17.63 |
| Alexandr V. Kostochka | 3 | 682 | 89.87 |
| Douglas B. West | 4 | 1176 | 185.69 |
| Xuding Zhu | 5 | 1883 | 190.19 |