The pseudoforest analogue for the strong nine dragon tree conjecture is true

DOI10.1016/J.JCTB.2020.07.001MaRDI QIDQ2200931zbMATH OpenOpenAlexFDO

Authors Logan Grout, Benjamin Moore

Publication date 24 September 2020

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

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

zbMATH Keywords

graph decompositionspseudoforestsstrong nine dragon tree

Mathematics Subject Classification ID

Trees (05C05) Vertex degrees (05C07) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: We prove that for any positive integers $k$ and $d$, if a graph $G$ has maximum average degree at most $2k+frac2dd+k+1$, then $G$ decomposes into $k+1$ pseudoforests $C_1,ldots,C_{k+1}$ such that there is an $i$ such that for every connected component $C$ of $C_i$, we have that $e(C)leqd$.

Recommendations

• Decomposing a graph into forests: the nine dragon tree conjecture is true
• Digraph analogues for the Nine Dragon Tree Conjecture
• Decomposition of sparse graphs into forests: the nine dragon tree conjecture for \(k \leq 2\)
• A proof of the rooted tree alternative conjecture
• A tree version of Kőnig's theorem
• Strong Chang's conjecture and the tree property at \(\omega_{2}\)
• Grundy domination of forests and the strong product conjecture
• On conjectures of Minkowski and Woods for n = 9
• On strict-double-bound numbers of complete pseudo-regular trees
• scientific article; zbMATH DE number 951849

Cites work

• Decomposing a graph into forests
• Decomposing a graph into forests and a matching
• Decomposing a graph into forests: the nine dragon tree conjecture is true
• Decomposing a graph into pseudoforests with one having bounded degree
• Decomposition of Finite Graphs Into Forests
• Decomposition of sparse graphs into forests and a graph with bounded degree
• Graph theory
• On the degrees of the vertices of a directed graph

Cited in

(9)

• Decreasing the maximum average degree by deleting an independent set or a \(d\)-degenerate subgraph
• Decomposition of sparse graphs into forests: the nine dragon tree conjecture for \(k \leq 2\)
• Decomposing a graph into pseudoforests with one having bounded degree
• Digraph analogues for the Nine Dragon Tree Conjecture
• The spectral radius, maximum average degree and cycles of consecutive lengths of graphs
• Beyond the pseudoforest strong nine dragon tree theorem
• The overfull nine dragon tree conjecture is true
• Resolution of the Kohayakawa-Kreuter conjecture
• Decomposing a graph into forests: the nine dragon tree conjecture is true

This page was built for publication: The pseudoforest analogue for the strong nine dragon tree conjecture is true

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