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

DOI10.1016/J.JCTB.2016.09.004zbMATH Open1350.05084arXiv1502.04755OpenAlexW2118439290MaRDI QIDQ345121FDOQ345121

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)

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)$.

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

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

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)

Cites Work

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

Cited In (11)

• 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
• I,F-partitions of sparse graphs
• Decomposing 4-connected planar triangulations into two trees and one path
• Digraph analogues for the Nine Dragon Tree Conjecture
• Covering a graph by forests and a matching
• The pseudoforest analogue for the strong nine dragon tree conjecture is true
• An enhancement of Nash-Williams' theorem on edge arboricity of graphs
• Decomposing a graph into pseudoforests with one having bounded degree
• An extension of Nash-Williams and Tutte's theorem

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)