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

详细信息    查看全文

• 作者：Min Chen^a ; ¹ ; ^{chenmin@zjnu.edu.cn} ; Seog-Jin Kim^b ; ² ; ^{skim12@konkuk.ac.kr} ; Alexandr V. Kostochka^a ; ^c ; ³ ; ^{kostochk@math.uiuc.edu} ; Douglas B. West^a ; ^c ; ⁴ ; ^{west@math.uiuc.edu} ; Xuding Zhu^a ; ⁵ ; ^{xdzhu@zjnu.edu.cn}
• 关键词：Nine Dragon Tree Conjecture ; Arboricity ; Nash-Williams Arboricity Formula ; Fractional arboricity ; Forest ; Graph decomposition ; Discharging method ; Sparse graph
• 刊名：Journal of Combinatorial Theory, Series B
• 出版年：2017
• 出版时间：January 2017
• 年：2017
• 卷：122
• 期：Complete
• 页码：741-756
• 全文大小：412 K
• 卷排序：122

文摘

For a loopless multigraph G, the fractional arboricity  Arb(G)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+1k+1 forests with one having maximum degree at most d  . The conjecture was previously proved for d=k+1d=k+1 and for k=1k=1 when d≤6d≤6. We prove it for all d   when k≤2k≤2, except for (k,d)=(2,1)(k,d)=(2,1).