Name
Abstract | ||
|---|---|---|
For a loopless multigraph G, the fractional arboricity Arb(G) is the maximum of <mml:mfrac>|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+d/k+d+1, then G decomposes into k+1 forests with one having maximum degree at most d. The conjecture was previously proved for (k,d){(1,1),(1,2)}; we prove it for d=k+1 and when k=1 and d6. For (k,d)=(1,2), we can further restrict one forest to have at most two edges in each component. For general (k,d), we prove weaker conclusions. If d>k, then Arb (G)k+d/k+d+1</mml:mfrac> implies that G decomposes into k forests plus a multigraph (not necessarily a forest) with maximum degree at most d. If dk, then Arb (G)k+d/2k+2</mml:mfrac> implies that G decomposes into k+1 forests, one having maximum degree at most d. Our results generalize earlier results about decomposition of sparse planar graphs. (C) 2013 Wiley Periodicals, Inc. J. Graph Theory 74: 369-391, 2013 |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1002/jgt.21711 | JOURNAL OF GRAPH THEORY |
Keywords | Field | DocType |
graph decomposition,forest,fractional arboricity,maximum average degree,discharging | Discrete mathematics,Topology,Combinatorics,Multigraph,Vertex (geometry),Generalization,Degree (graph theory),Conjecture,Arboricity,Mathematics,Planar graph,Bounded function | Journal |
Volume | Issue | ISSN |
74.0 | 4.0 | 0364-9024 |
Citations | PageRank | References |
9 | 0.73 | 9 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Seog-Jin Kim | 1 | 151 | 17.63 |
| Alexandr V. Kostochka | 2 | 682 | 89.87 |
| Douglas B. West | 3 | 1176 | 185.69 |
| Hehui Wu | 4 | 64 | 7.40 |
| Xuding Zhu | 5 | 1883 | 190.19 |