Product structure of graphs with an excluded minor
This paper shows that Kt-minor-free (and Ks,t-minor-free) graphs G are subgraphs of products of a tree-like graph H (of bounded treewidth) and a complete graph Km. Our results include optimal bounds on the treewidth of H and optimal bounds (to within a constant factor) on m in terms of the number of...
| Main Authors: | , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
American Mathematical Society
2024
|
| Summary: | This paper shows that Kt-minor-free (and Ks,t-minor-free) graphs G are
subgraphs of products of a tree-like graph H (of bounded treewidth) and a
complete graph Km. Our results include optimal bounds on the treewidth of H
and optimal bounds (to within a constant factor) on m in terms of the number of
vertices of G and the treewidth of G. These results follow from a more general
theorem whose corollaries include a strengthening of the celebrated separator
theorem of Alon, Seymour, and Thomas [J. Amer. Math. Soc. 1990] and the
Planar Graph Product Structure Theorem of Dujmović et al. [J. ACM 2020]. |
|---|