Treewidth, Hadwiger Number, and Induced Minors
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914988594036736 |
|---|---|
| author | Campbell, Rutger Davies, James Distel, Marc Frederickson, Bryce Gollin, J. Pascal Hendrey, Kevin Hickingbotham, Robert Wiederrecht, Sebastian Wood, David R. Yepremyan, Liana |
| author_facet | Campbell, Rutger Davies, James Distel, Marc Frederickson, Bryce Gollin, J. Pascal Hendrey, Kevin Hickingbotham, Robert Wiederrecht, Sebastian Wood, David R. Yepremyan, Liana |
| contents | Treewidth and Hadwiger number are two of the most important parameters in structural graph theory.
This paper studies graph classes in which large treewidth implies the existence of a large complete graph minor.
To formalise this, we say that a graph class $\mathcal{G}$ is (tw,had)-bounded if there is a function $f$ (called the (tw,had)-bounding function) such that tw$(G)$ $\leq$ $f$(had$(G)$) for every graph $G \in \mathcal{G}$.
We characterise (tw,had)-bounded graph classes as those that exclude some planar graph as an induced minor, and use this characterisation to show that every proper vertex-minor-closed class is (tw,had)-bounded. Furthermore, we demonstrate that any (tw,had)-bounded graph class has a (tw,had)-bounding function in O(had$(G)^9$polylog(had$(G)$)). Our bound comes from the bound for the Grid Minor Theorem given by Chuzhoy and Tan, and any quantitative improvement to their result will lead directly to an improvement to our result.
More strongly, we conjecture that every (tw,had)-bounded graph class has a linear (tw,had)-bounding function.
In support of this conjecture, we show that it holds for the class of outer-string graphs, and for a natural generalisation of outer-string graphs: intersection graphs of strings rooted at the boundary of a fixed surface. We also verify our conjecture for low-rank perturbations of circle graphs, which is an important step towards verifying it for all proper vertex-minor-closed classes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_19295 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Treewidth, Hadwiger Number, and Induced Minors Campbell, Rutger Davies, James Distel, Marc Frederickson, Bryce Gollin, J. Pascal Hendrey, Kevin Hickingbotham, Robert Wiederrecht, Sebastian Wood, David R. Yepremyan, Liana Combinatorics 05C99 G.2.2 Treewidth and Hadwiger number are two of the most important parameters in structural graph theory. This paper studies graph classes in which large treewidth implies the existence of a large complete graph minor. To formalise this, we say that a graph class $\mathcal{G}$ is (tw,had)-bounded if there is a function $f$ (called the (tw,had)-bounding function) such that tw$(G)$ $\leq$ $f$(had$(G)$) for every graph $G \in \mathcal{G}$. We characterise (tw,had)-bounded graph classes as those that exclude some planar graph as an induced minor, and use this characterisation to show that every proper vertex-minor-closed class is (tw,had)-bounded. Furthermore, we demonstrate that any (tw,had)-bounded graph class has a (tw,had)-bounding function in O(had$(G)^9$polylog(had$(G)$)). Our bound comes from the bound for the Grid Minor Theorem given by Chuzhoy and Tan, and any quantitative improvement to their result will lead directly to an improvement to our result. More strongly, we conjecture that every (tw,had)-bounded graph class has a linear (tw,had)-bounding function. In support of this conjecture, we show that it holds for the class of outer-string graphs, and for a natural generalisation of outer-string graphs: intersection graphs of strings rooted at the boundary of a fixed surface. We also verify our conjecture for low-rank perturbations of circle graphs, which is an important step towards verifying it for all proper vertex-minor-closed classes. |
| title | Treewidth, Hadwiger Number, and Induced Minors |
| topic | Combinatorics 05C99 G.2.2 |
| url | https://arxiv.org/abs/2410.19295 |