The Excluded Tree Minor Theorem Revisited
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866911749661261824 |
|---|---|
| author | Dujmović, Vida Hickingbotham, Robert Joret, Gwenaël Micek, Piotr Morin, Pat Wood, David R. |
| author_facet | Dujmović, Vida Hickingbotham, Robert Joret, Gwenaël Micek, Piotr Morin, Pat Wood, David R. |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2303_14970 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | The Excluded Tree Minor Theorem Revisited Dujmović, Vida Hickingbotham, Robert Joret, Gwenaël Micek, Piotr Morin, Pat Wood, David R. Combinatorics Discrete Mathematics 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. |
| title | The Excluded Tree Minor Theorem Revisited |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2303.14970 |