Induced subgraphs and tree decompositions XVII. Anticomplete sets of large treewidth
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866918213860720640 |
|---|---|
| author | Chudnovsky, Maria Hajebi, Sepehr Spirkl, Sophie |
| author_facet | Chudnovsky, Maria Hajebi, Sepehr Spirkl, Sophie |
| contents | Two sets $X, Y$ of vertices in a graph $G$ are "anticomplete" if $X\cap Y=\varnothing$ and there is no edge in $G$ with an end in $X$ and an end in $Y$. We prove that every graph $G$ of sufficiently large treewidth contains two anticomplete sets of vertices each inducing a subgraph of large treewidth unless $G$ contains, as an induced subgraph, a highly structured graph of large treewidth that is an obvious counterexample to this statement. These are: complete graphs, complete bipartite graphs and "interrupted $s$-constellations." The latter is a slightly adjusted version of a well-known construction by Bonamy et al. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_11842 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Induced subgraphs and tree decompositions XVII. Anticomplete sets of large treewidth Chudnovsky, Maria Hajebi, Sepehr Spirkl, Sophie Combinatorics Two sets $X, Y$ of vertices in a graph $G$ are "anticomplete" if $X\cap Y=\varnothing$ and there is no edge in $G$ with an end in $X$ and an end in $Y$. We prove that every graph $G$ of sufficiently large treewidth contains two anticomplete sets of vertices each inducing a subgraph of large treewidth unless $G$ contains, as an induced subgraph, a highly structured graph of large treewidth that is an obvious counterexample to this statement. These are: complete graphs, complete bipartite graphs and "interrupted $s$-constellations." The latter is a slightly adjusted version of a well-known construction by Bonamy et al. |
| title | Induced subgraphs and tree decompositions XVII. Anticomplete sets of large treewidth |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2411.11842 |