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

Research output: Contribution to journalArticlepeer-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 languageEnglish (US)
Pages (from-to)741-756
Number of pages16
JournalJournal of Combinatorial Theory. Series B
Volume122
DOIs
StatePublished - 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

Fingerprint Dive into the research topics of 'Decomposition of sparse graphs into forests: The Nine Dragon Tree Conjecture for k ≤ 2'. Together they form a unique fingerprint.

Cite this