Induced subgraphs and tree decompositions XIII. Basic obstructions in $\mathcal{H}$-free graphs for finite $\mathcal{H}$
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912135443906560 |
|---|---|
| author | Alecu, Bogdan Chudnovsky, Maria Hajebi, Sepehr Spirkl, Sophie |
| author_facet | Alecu, Bogdan Chudnovsky, Maria Hajebi, Sepehr Spirkl, Sophie |
| contents | Unlike minors, the induced subgraph obstructions to bounded treewidth come in a large variety, including, for every $t\geq 1$, the $t$-basic obstructions: the graphs $K_{t+1}$ and $K_{t,t}$, along with the subdivisions of the $t$-by-$t$ wall and their line graphs. But this list is far from complete. The simplest example of a ''non-basic'' obstruction is due to Pohoata and Davies (independently). For every $n \geq 1$, they construct certain graphs of treewidth $n$ and with no $3$-basic obstruction as an induced subgraph, which we call $n$-arrays. Let us say a graph class $\mathcal{G}$ is clean if the only obstructions to bounded treewidth in $\mathcal{G}$ are in fact the basic ones. It follows that a full description of the induced subgraph obstructions to bounded treewidth is equivalent to a characterization of all families $\mathcal{H}$ of graphs for which the class of all $\mathcal{H}$-free graphs is clean (a graph $G$ is $\mathcal{H}$-free if no induced subgraph of $G$ is isomorphic to any graph in $\mathcal{H}$). This remains elusive, but there is an immediate necessary condition: if $\mathcal{H}$-free graphs are clean, then there are only finitely many integers $n\geq 1$ such that there is an $n$-array which is $\mathcal{H}$-free. The above necessary condition is not sufficient in general. However, the situation turns out to be different if $\mathcal{H}$ is finite: we prove that for every finite set $\mathcal{H}$ of graphs, the class of all $\mathcal{H}$-free graphs is clean if and only if there is no $\mathcal{H}$-free $n$-array except possibly for finitely many values of $n$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2311_05066 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Induced subgraphs and tree decompositions XIII. Basic obstructions in $\mathcal{H}$-free graphs for finite $\mathcal{H}$ Alecu, Bogdan Chudnovsky, Maria Hajebi, Sepehr Spirkl, Sophie Combinatorics Unlike minors, the induced subgraph obstructions to bounded treewidth come in a large variety, including, for every $t\geq 1$, the $t$-basic obstructions: the graphs $K_{t+1}$ and $K_{t,t}$, along with the subdivisions of the $t$-by-$t$ wall and their line graphs. But this list is far from complete. The simplest example of a ''non-basic'' obstruction is due to Pohoata and Davies (independently). For every $n \geq 1$, they construct certain graphs of treewidth $n$ and with no $3$-basic obstruction as an induced subgraph, which we call $n$-arrays. Let us say a graph class $\mathcal{G}$ is clean if the only obstructions to bounded treewidth in $\mathcal{G}$ are in fact the basic ones. It follows that a full description of the induced subgraph obstructions to bounded treewidth is equivalent to a characterization of all families $\mathcal{H}$ of graphs for which the class of all $\mathcal{H}$-free graphs is clean (a graph $G$ is $\mathcal{H}$-free if no induced subgraph of $G$ is isomorphic to any graph in $\mathcal{H}$). This remains elusive, but there is an immediate necessary condition: if $\mathcal{H}$-free graphs are clean, then there are only finitely many integers $n\geq 1$ such that there is an $n$-array which is $\mathcal{H}$-free. The above necessary condition is not sufficient in general. However, the situation turns out to be different if $\mathcal{H}$ is finite: we prove that for every finite set $\mathcal{H}$ of graphs, the class of all $\mathcal{H}$-free graphs is clean if and only if there is no $\mathcal{H}$-free $n$-array except possibly for finitely many values of $n$. |
| title | Induced subgraphs and tree decompositions XIII. Basic obstructions in $\mathcal{H}$-free graphs for finite $\mathcal{H}$ |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2311.05066 |