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

DOI10.1016/J.JCTB.2020.07.001zbMATH Open1448.05163arXiv1905.02600OpenAlexW3043348258MaRDI QIDQ2200931FDOQ2200931

Authors: Logan Grout, Benjamin Moore 

Publication date: 24 September 2020

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

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

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

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

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)

Cites Work

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

Cited In (6)

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

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)