Decomposition of sparse graphs into forests: The Nine Dragon Tree Conjecture for k ≤ 2

Min Chen; Seog Jin Kim; Alexandr V. Kostochka; Douglas B. West; Xuding Zhu

doi:10.1016/j.jctb.2016.09.004

Decomposition of sparse graphs into forests: The Nine Dragon Tree Conjecture for k ≤ 2

Min Chen, Seog Jin Kim, Alexandr V. Kostochka, Douglas B. West, Xuding Zhu

Mathematics

Research output: Contribution to journal › Article › peer-review

Abstract

For a loopless multigraph G, the fractional arboricity Arb(G) is the maximum of [formula presented] 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+[formula presented], 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).

Original language	English (US)
Pages (from-to)	741-756
Number of pages	16
Journal	Journal of Combinatorial Theory. Series B
Volume	122
DOIs	https://doi.org/10.1016/j.jctb.2016.09.004
State	Published - Jan 1 2017

Keywords

Arboricity
Discharging method
Forest
Fractional arboricity
Graph decomposition
Nash-Williams Arboricity Formula
Nine Dragon Tree Conjecture
Sparse graph

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Online availability

10.1016/j.jctb.2016.09.004

Library availability

Discover UIUC Full Text

Cite this

@article{02085e86fa0b403186d0e1805d944640,

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 [formula presented] 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+[formula presented], 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).",

keywords = "Arboricity, Discharging method, Forest, Fractional arboricity, Graph decomposition, Nash-Williams Arboricity Formula, Nine Dragon Tree Conjecture, Sparse graph",

author = "Min Chen and Kim, {Seog Jin} and Kostochka, {Alexandr V.} and West, {Douglas B.} and Xuding Zhu",

note = "Research supported by CNSF grant 11571319.",

year = "2017",

month = jan,

day = "1",

doi = "10.1016/j.jctb.2016.09.004",

language = "English (US)",

volume = "122",

pages = "741--756",

journal = "Journal of Combinatorial Theory. Series B",

issn = "0095-8956",

publisher = "Academic Press Inc.",

}

TY - JOUR

T1 - Decomposition of sparse graphs into forests

T2 - The Nine Dragon Tree Conjecture for k ≤ 2

AU - Chen, Min

AU - Kim, Seog Jin

AU - Kostochka, Alexandr V.

AU - West, Douglas B.

AU - Zhu, Xuding

N1 - Research supported by CNSF grant 11571319.

PY - 2017/1/1

Y1 - 2017/1/1

N2 - For a loopless multigraph G, the fractional arboricity Arb(G) is the maximum of [formula presented] 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+[formula presented], 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).

AB - For a loopless multigraph G, the fractional arboricity Arb(G) is the maximum of [formula presented] 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+[formula presented], 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).

KW - Arboricity

KW - Discharging method

KW - Forest

KW - Fractional arboricity

KW - Graph decomposition

KW - Nash-Williams Arboricity Formula

KW - Nine Dragon Tree Conjecture

KW - Sparse graph

UR - http://www.scopus.com/inward/record.url?scp=84994803435&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84994803435&partnerID=8YFLogxK

U2 - 10.1016/j.jctb.2016.09.004

DO - 10.1016/j.jctb.2016.09.004

M3 - Article

AN - SCOPUS:84994803435

SN - 0095-8956

VL - 122

SP - 741

EP - 756

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

ER -