Back to Search Start Over

The Excluded Tree Minor Theorem Revisited

Authors :
Dujmović, Vida
Hickingbotham, Robert
Joret, Gwenaël
Micek, Piotr
Morin, Pat
Wood, David R.
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