Salvato in:
| Autori principali: | , , , , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2022
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2212.08739 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916465133748224 |
|---|---|
| author | Distel, Marc Dujmović, Vida Eppstein, David Hickingbotham, Robert Joret, Gwenaël Micek, Piotr Morin, Pat Seweryn, Michał T. Wood, David R. |
| author_facet | Distel, Marc Dujmović, Vida Eppstein, David Hickingbotham, Robert Joret, Gwenaël Micek, Piotr Morin, Pat Seweryn, Michał T. Wood, David R. |
| contents | Alon, Seymour and Thomas [1990] proved that every $n$-vertex graph excluding $K_t$ as a minor has treewidth less than $t^{3/2}\sqrt{n}$. Illingworth, Scott and Wood [2022] recently refined this result by showing that every such graph is a subgraph of some graph with treewidth $t-2$, where each vertex is blown up by a complete graph of order $O(\sqrt{tn})$. Solving an open problem of Illingworth, Scott and Wood [2022], we prove that the treewidth bound can be reduced to $4$ while keeping blowups of order $O_t(\sqrt{n})$. As an extension of the Lipton--Tarjan theorem, in the case of planar graphs, we show that the treewidth can be further reduced to $2$, which is best possible. We generalise this result for $K_{3,t}$-minor-free graphs, with blowups of order $O(t\sqrt{n})$. This setting includes graphs embeddable on any fixed surface. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2212_08739 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Product structure extension of the Alon--Seymour--Thomas theorem Distel, Marc Dujmović, Vida Eppstein, David Hickingbotham, Robert Joret, Gwenaël Micek, Piotr Morin, Pat Seweryn, Michał T. Wood, David R. Combinatorics Alon, Seymour and Thomas [1990] proved that every $n$-vertex graph excluding $K_t$ as a minor has treewidth less than $t^{3/2}\sqrt{n}$. Illingworth, Scott and Wood [2022] recently refined this result by showing that every such graph is a subgraph of some graph with treewidth $t-2$, where each vertex is blown up by a complete graph of order $O(\sqrt{tn})$. Solving an open problem of Illingworth, Scott and Wood [2022], we prove that the treewidth bound can be reduced to $4$ while keeping blowups of order $O_t(\sqrt{n})$. As an extension of the Lipton--Tarjan theorem, in the case of planar graphs, we show that the treewidth can be further reduced to $2$, which is best possible. We generalise this result for $K_{3,t}$-minor-free graphs, with blowups of order $O(t\sqrt{n})$. This setting includes graphs embeddable on any fixed surface. |
| title | Product structure extension of the Alon--Seymour--Thomas theorem |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2212.08739 |