Product structure of graphs with an excluded minor
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2021
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910688265371648 |
|---|---|
| author | Illingworth, Freddie Scott, Alex Wood, David R. |
| author_facet | Illingworth, Freddie Scott, Alex Wood, David R. |
| contents | This paper shows that $K_t$-minor-free (and $K_{s, t}$-minor-free) graphs $G$ are subgraphs of products of a tree-like graph $H$ (of bounded treewidth) and a complete graph $K_m$. 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]. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2104_06627 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Product structure of graphs with an excluded minor Illingworth, Freddie Scott, Alex Wood, David R. Combinatorics This paper shows that $K_t$-minor-free (and $K_{s, t}$-minor-free) graphs $G$ are subgraphs of products of a tree-like graph $H$ (of bounded treewidth) and a complete graph $K_m$. 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]. |
| title | Product structure of graphs with an excluded minor |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2104.06627 |