Beyond the pseudoforest strong Nine Dragon Tree theorem
Mies S, Moore B, Smith-Roberge E. 2025. Beyond the pseudoforest strong Nine Dragon Tree theorem. European Journal of Combinatorics. 130(12), 104214.
Download (ext.)
Journal Article
| Epub ahead of print
| English
Scopus indexed
Author
Mies, Sebastian;
Moore, BenjaminISTA;
Smith-Roberge, Evelyne
Corresponding author has ISTA affiliation
Department
Abstract
The pseudoforest version of the Strong Nine Dragon Tree Conjecture states that if a graph G has maximum average degree mad(G) = 2 maxH⊆G e(H)/v(H) at most 2(k + d/d+k+1), then it has a decomposition into k + 1 pseudoforests where in one pseudoforest F the components of F have at most d edges. This was proven in 2020 in Grout and Moore (2020). We strengthen this
theorem by showing that we can find such a decomposition where additionally F is acyclic, the diameter of the components of F is at most 2ℓ + 2, where ℓ =⌊d−1/k+1⌋, and at most 2ℓ + 1 if
d ≡ 1 mod (k + 1). Furthermore, for any component K of F and any z ∈ N, we have diam(K) ≤ 2z if e(K) ≥ d − z(k − 1) + 1. We also show that both diameter bounds are best possible as an
extension for both the Strong Nine Dragon Tree Conjecture for pseudoforests and its original conjecture for forests. In fact, they are still optimal even if we only enforce F to have any constant maximum degree, instead of enforcing every component of F to have at most d edges.
Publishing Year
Date Published
2025-07-08
Journal Title
European Journal of Combinatorics
Publisher
Elsevier
Acknowledgement
This work was completed while Benjamin Moore was a postdoc at Charles University, supported by project 22-17398S (Flows and cycles in graphs on surfaces) of Czech Science Foundation, Czechia.
Volume
130
Issue
12
Article Number
104214
ISSN
IST-REx-ID
Cite this
Mies S, Moore B, Smith-Roberge E. Beyond the pseudoforest strong Nine Dragon Tree theorem. European Journal of Combinatorics. 2025;130(12). doi:10.1016/j.ejc.2025.104214
Mies, S., Moore, B., & Smith-Roberge, E. (2025). Beyond the pseudoforest strong Nine Dragon Tree theorem. European Journal of Combinatorics. Elsevier. https://doi.org/10.1016/j.ejc.2025.104214
Mies, Sebastian, Benjamin Moore, and Evelyne Smith-Roberge. “Beyond the Pseudoforest Strong Nine Dragon Tree Theorem.” European Journal of Combinatorics. Elsevier, 2025. https://doi.org/10.1016/j.ejc.2025.104214.
S. Mies, B. Moore, and E. Smith-Roberge, “Beyond the pseudoforest strong Nine Dragon Tree theorem,” European Journal of Combinatorics, vol. 130, no. 12. Elsevier, 2025.
Mies S, Moore B, Smith-Roberge E. 2025. Beyond the pseudoforest strong Nine Dragon Tree theorem. European Journal of Combinatorics. 130(12), 104214.
Mies, Sebastian, et al. “Beyond the Pseudoforest Strong Nine Dragon Tree Theorem.” European Journal of Combinatorics, vol. 130, no. 12, 104214, Elsevier, 2025, doi:10.1016/j.ejc.2025.104214.
All files available under the following license(s):
Creative Commons Attribution 4.0 International Public License (CC-BY 4.0):
Link(s) to Main File(s)
Access Level

Export
Marked PublicationsOpen Data ISTA Research Explorer
Web of Science
View record in Web of Science®Sources
arXiv 2310.00931