Quickly excluding an apex-forest
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866912308379254784 |
|---|---|
| author | Hodor, Jędrzej La, Hoang Micek, Piotr Rambaud, Clément |
| author_facet | Hodor, Jędrzej La, Hoang Micek, Piotr Rambaud, Clément |
| contents | We give a short proof that for every apex-forest $X$ on at least two vertices, graphs excluding $X$ as a minor have layered pathwidth at most $2|V(X)|-3$. This improves upon a result by Dujmović, Eppstein, Joret, Morin, and Wood (SIDMA, 2020). Our main tool is a structural result about graphs excluding a forest as a rooted minor, which is of independent interest. We develop similar tools for treedepth and treewidth. We discuss implications for Erdős-Pósa properties of rooted models of minors in graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_17306 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Quickly excluding an apex-forest Hodor, Jędrzej La, Hoang Micek, Piotr Rambaud, Clément Combinatorics Discrete Mathematics We give a short proof that for every apex-forest $X$ on at least two vertices, graphs excluding $X$ as a minor have layered pathwidth at most $2|V(X)|-3$. This improves upon a result by Dujmović, Eppstein, Joret, Morin, and Wood (SIDMA, 2020). Our main tool is a structural result about graphs excluding a forest as a rooted minor, which is of independent interest. We develop similar tools for treedepth and treewidth. We discuss implications for Erdős-Pósa properties of rooted models of minors in graphs. |
| title | Quickly excluding an apex-forest |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2404.17306 |