No CrossRef data available.
Article contents
The Excluded Tree Minor Theorem Revisited
Published online by Cambridge University Press: 27 September 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.
- Type
- Paper
- Information
- Copyright
- © The Author(s), 2023. Published by Cambridge University Press
Footnotes
Vida Dujmović: Research supported by NSERC, and a Gordon Preston Fellowship from the School of Mathematics at Monash University.
Robert Hickingbotham: Research supported by Australian Government Research Training Program Scholarships.
Gwenaël Joret: Supported by the Australian Research Council, and by a CDR grant and a PDR from the National Fund for Scientific Research (FNRS).
Pat Morin: Research supported by NSERC.
David R. Wood: Research supported by the Australian Research Council.