Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2410.16495 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917279837454336 |
|---|---|
| author | Chudnovsky, Maria Hajebi, Sepehr Spirkl, Sophie |
| author_facet | Chudnovsky, Maria Hajebi, Sepehr Spirkl, Sophie |
| contents | We prove that for every graph $G$ with a sufficiently large complete bipartite induced minor, either $G$ has an induced minor isomorphic to a large wall, or $G$ contains a large constellation; that is, a complete bipartite induced minor model such that on one side of the bipartition, each branch set is a singleton, and on the other side, each branch set induces a path.
We further refine this theorem by characterizing the unavoidable induced subgraphs of large constellations as two types of highly structured constellations. These results will be key ingredients in several forthcoming papers of this series. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_16495 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Induced subgraphs and tree decompositions XVI. Complete bipartite induced minors Chudnovsky, Maria Hajebi, Sepehr Spirkl, Sophie Combinatorics We prove that for every graph $G$ with a sufficiently large complete bipartite induced minor, either $G$ has an induced minor isomorphic to a large wall, or $G$ contains a large constellation; that is, a complete bipartite induced minor model such that on one side of the bipartition, each branch set is a singleton, and on the other side, each branch set induces a path. We further refine this theorem by characterizing the unavoidable induced subgraphs of large constellations as two types of highly structured constellations. These results will be key ingredients in several forthcoming papers of this series. |
| title | Induced subgraphs and tree decompositions XVI. Complete bipartite induced minors |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2410.16495 |