Decomposition of sparse graphs into forests: the nine dragon tree conjecture for k 2

DOI10.1016/J.JCTB.2016.09.004MaRDI QIDQ345121zbMATH OpenOpenAlexFDO

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

Publication date 25 November 2016

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1502.04755

zbMATH Keywords

arboricitygraph decompositionforestdischarging methodfractional arboricityNash-Williams arboricity formulanine dragon tree conjecturesparse graph

Mathematics Subject Classification ID

Density (toughness, etc.) (05C42) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: For a loopless multigraph $G$, the fractional arboricity $Arb(G)$ is the maximum of $frac|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)lek+fracdk+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 $dle6$. We prove it for all $d$ when $kle2$, except for $(k,d)=(2,1)$.

Recommendations

• Decomposition of sparse graphs into forests and a graph with bounded degree
• Decomposing a graph into forests: the nine dragon tree conjecture is true
• Decomposing a graph into forests and a matching
• Covering a graph by forests and a matching
• The pseudoforest analogue for the strong nine dragon tree conjecture is true

Cites work

• Covering planar graphs with forests
• Covering planar graphs with forests, one having bounded maximum degree
• Decomposing a graph into forests
• Decomposing a planar graph into a forest and a subgraph of restricted maximum degree
• Decomposing a planar graph with girth 9 into a forest and a matching
• Decomposing a planar graph with girth at least 8 into a forest and a matching
• Decomposition of Finite Graphs Into Forests
• Decomposition of sparse graphs into forests and a graph with bounded degree
• Decomposition of sparse graphs, with application to game coloring number
• Decompositions of quadrangle-free planar graphs
• Edge-partitions of planar graphs and their game coloring numbers
• Graphes équilibrés et arboricité rationnelle. (Balanced graphs and rational arboricity)
• Partitioning a planar graph of girth 10 into a forest and a matching
• Planar graphs decomposable into a forest and a matching

Cited in

(12)

• Decomposing 4-connected planar triangulations into two trees and one path
• Decomposing a graph into pseudoforests with one having bounded degree
• An extension of Nash-Williams and Tutte's theorem
• Covering a graph by forests and a matching
• The strong nine dragon tree conjecture is true for \(d \le k + 1\)
• Digraph analogues for the Nine Dragon Tree Conjecture
• Decomposing a graph into forests: the nine dragon tree conjecture is true
• Decomposing a graph into forests and a matching
• Decomposition of sparse graphs into forests and a graph with bounded degree
• The pseudoforest analogue for the strong nine dragon tree conjecture is true
• An enhancement of Nash-Williams' theorem on edge arboricity of graphs
• I,F-partitions of sparse graphs

This page was built for publication: Decomposition of sparse graphs into forests: the nine dragon tree conjecture for \(k \leq 2\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q345121)