Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2309.12227 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909565651517440 |
|---|---|
| author | Alecu, Bogdan Chudnovsky, Maria Hajebi, Sepehr Spirkl, Sophie |
| author_facet | Alecu, Bogdan Chudnovsky, Maria Hajebi, Sepehr Spirkl, Sophie |
| contents | Given an integer $c\in \mathbb{N}$, we say a graph $G$ is $c$-pinched if $G$ does not contain an induced subgraph consisting of $c$ cycles, all going through a single common vertex and otherwise pairwise disjoint and with no edges between them. What can be said about the structure of $c$-pinched graphs?
For instance, $1$-pinched graphs are exactly graphs of treewidth $1$. However, bounded treewidth for $c>1$ is immediately seen to be a false hope because complete graphs, complete bipartite graphs, subdivided walls and line graphs of subdivided walls are all examples of $2$-pinched graphs with arbitrarily large treewidth. There is even a fifth obstruction for larger values of $c$, discovered by Pohoata and later independently by Davies, consisting of $3$-pinched graphs with unbounded treewidth and no large induced subgraph isomorphic to any of the first four obstructions.
We fuse the above five examples into a grid-type theorem fully describing the unavoidable induced subgraphs of pinched graphs with large treewidth. More precisely, we prove that for every integer $c\in \mathbb{N}$, a $c$-pinched graph $G$ has large treewidth if and only if $G$ contains one of the following as an induced subgraph: a large complete graph, a large complete bipartite graph, a subdivision of a large wall, the line-graph of a subdivision of a large wall, or a large graph from the Pohoata-Davies construction. Our main result also generalizes to an extension of pinched graphs where the lengths of excluded cycles are lower-bounded. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2309_12227 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Induced subgraphs and tree decompositions XII. Grid theorem for pinched graphs Alecu, Bogdan Chudnovsky, Maria Hajebi, Sepehr Spirkl, Sophie Combinatorics Given an integer $c\in \mathbb{N}$, we say a graph $G$ is $c$-pinched if $G$ does not contain an induced subgraph consisting of $c$ cycles, all going through a single common vertex and otherwise pairwise disjoint and with no edges between them. What can be said about the structure of $c$-pinched graphs? For instance, $1$-pinched graphs are exactly graphs of treewidth $1$. However, bounded treewidth for $c>1$ is immediately seen to be a false hope because complete graphs, complete bipartite graphs, subdivided walls and line graphs of subdivided walls are all examples of $2$-pinched graphs with arbitrarily large treewidth. There is even a fifth obstruction for larger values of $c$, discovered by Pohoata and later independently by Davies, consisting of $3$-pinched graphs with unbounded treewidth and no large induced subgraph isomorphic to any of the first four obstructions. We fuse the above five examples into a grid-type theorem fully describing the unavoidable induced subgraphs of pinched graphs with large treewidth. More precisely, we prove that for every integer $c\in \mathbb{N}$, a $c$-pinched graph $G$ has large treewidth if and only if $G$ contains one of the following as an induced subgraph: a large complete graph, a large complete bipartite graph, a subdivision of a large wall, the line-graph of a subdivision of a large wall, or a large graph from the Pohoata-Davies construction. Our main result also generalizes to an extension of pinched graphs where the lengths of excluded cycles are lower-bounded. |
| title | Induced subgraphs and tree decompositions XII. Grid theorem for pinched graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2309.12227 |