The Excluded Tree Minor Theorem Revisited
share
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⊠ 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.
READ FULL TEXT