Excluding an apex-forest or a fan as quickly as possible
Abstract
We show that every graph $G$ excluding an apex-forest $H$ as a minor has layered pathwidth at most $|V(H)|-2$, and that every graph $G$ excluding an apex-linear forest (such as a fan) $H$ as a minor has layered treedepth at most $|V(H)|-2$. We further show that both bounds are optimal. These results improve on recent results of Hodor, La, Micek, and Rambaud (2025): The first result improves the previous best-known bound by a multiplicative factor of $2$, while the second strengthens a previous quadratic bound. In addition, we reduce from quadratic to linear the bound on the $S$-focused treedepth $\mathrm{td}(G,S)$ for graphs $G$ with a prescribed set of vertices $S$ excluding models of paths in which every branch set intersects~$S$.
Growth and citations
This paper is currently showing No growth state computed yet..
Citation metrics and growth state from academic sources (e.g. Semantic Scholar). See About for details.
Cited by (0)
No citing papers yet
Papers that cite this one will appear here once data is available.
View citations page →References (0)
No references in DB yet
References for this paper will appear here once ingested.
Related papers in Discrete Mathematics
- An Algorithm for Monitoring Edge-geodetic Sets in Chordal Graphs0 citations
- Factor-balancedness, linear recurrence, and factor complexity0 citations
- A Parametrized Complexity View on Robust Scheduling with Budgeted Uncertainty0 citations
Growth transitions
No transitions recorded yet
Growth state transitions will appear here once computed.