Excluding an apex-forest or a fan as quickly as possible
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866908809929162752 |
|---|---|
| author | Claus, Quentin Hodor, Jędrzej Joret, Gwenaël Morin, Pat |
| author_facet | Claus, Quentin Hodor, Jędrzej Joret, Gwenaël Morin, Pat |
| contents | 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$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_03833 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Excluding an apex-forest or a fan as quickly as possible Claus, Quentin Hodor, Jędrzej Joret, Gwenaël Morin, Pat Combinatorics Discrete Mathematics 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$. |
| title | Excluding an apex-forest or a fan as quickly as possible |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2602.03833 |