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
OA Open Access

Export

Marked Publications

Open Data ISTA Research Explorer

Web of Science

View record in Web of Science®

Sources

arXiv 2310.00931

Search this title in

Google Scholar