Bounds on treewidth via excluding disjoint unions of cycles
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913634271100928 |
|---|---|
| author | Hatzel, Meike Liu, Chun-Hung Reed, Bruce Wiederrecht, Sebastian |
| author_facet | Hatzel, Meike Liu, Chun-Hung Reed, Bruce Wiederrecht, Sebastian |
| contents | One of the fundamental results in graph minor theory is that for every planar graph~$H$, there is a minimum integer~$f(H)$ such that graphs with no minor isomorphic to~$H$ have treewidth at most~$f(H)$. The best known bound for an arbitrary planar $H$ is ${O(|V(H)|^9\operatorname{poly~log} |V(H)|)}$. We show that if $H$ is the disjoint union of cycles, then $f(H)$ is $O(|V(H)|\log^2 |V(H)|)$, which is a $\log|V(H)|$ factor away being optimal. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_01703 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Bounds on treewidth via excluding disjoint unions of cycles Hatzel, Meike Liu, Chun-Hung Reed, Bruce Wiederrecht, Sebastian Combinatorics Discrete Mathematics One of the fundamental results in graph minor theory is that for every planar graph~$H$, there is a minimum integer~$f(H)$ such that graphs with no minor isomorphic to~$H$ have treewidth at most~$f(H)$. The best known bound for an arbitrary planar $H$ is ${O(|V(H)|^9\operatorname{poly~log} |V(H)|)}$. We show that if $H$ is the disjoint union of cycles, then $f(H)$ is $O(|V(H)|\log^2 |V(H)|)$, which is a $\log|V(H)|$ factor away being optimal. |
| title | Bounds on treewidth via excluding disjoint unions of cycles |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2501.01703 |