Back to Search
Start Over
The Excluded Tree Minor Theorem Revisited
- Publication Year :
- 2023
- Publisher :
- arXiv, 2023.
-
Abstract
- We prove that for every tree $T$ of radius $h$, there is an integer $c$ such that every $T$-minor-free graph is contained in $H\boxtimes K_c$ for some graph $H$ with pathwidth at most $2h-1$. This is a qualitative strengthening of the Excluded Tree Minor Theorem of Robertson and Seymour (GM I). We show that radius is the right parameter to consider in this setting, and $2h-1$ is the best possible bound.
Details
- Database :
- OpenAIRE
- Accession number :
- edsair.doi.dedup.....ff8016a02675432023052d8a3ca84cca
- Full Text :
- https://doi.org/10.48550/arxiv.2303.14970