Unavoidable induced subgraphs in graphs with complete bipartite induced minors
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866915592624144384 |
|---|---|
| author | Chudnovsky, Maria Hatzel, Meike Korhonen, Tuukka Trotignon, Nicolas Wiederrecht, Sebastian |
| author_facet | Chudnovsky, Maria Hatzel, Meike Korhonen, Tuukka Trotignon, Nicolas Wiederrecht, Sebastian |
| contents | We prove that if a graph contains the complete bipartite graph $K_{134, 12}$ as an induced minor, then it contains a cycle of length at most~12 or a theta as an induced subgraph. With a longer and more technical proof, we prove that if a graph contains $K_{3, 4}$ as an induced minor, then it contains a triangle or a theta as an induced subgraph. Here, a \emph{theta} is a graph made of three internally vertex-disjoint chordless paths $P_1 = a \dots b$, $P_2 = a \dots b$, $P_3 = a \dots b$, each of length at least two, such that no edges exist between the paths except the three edges incident to $a$ and the three edges incident to $b$.
A consequence is that excluding a grid and a complete bipartite graph as induced minors is not enough to guarantee a bounded tree-independence number, or even that the treewidth is bounded by a function of the size of the maximum clique, because the existence of graphs with large treewidth that contain no triangles or thetas as induced subgraphs is already known (the so-called layered wheels). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_01879 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Unavoidable induced subgraphs in graphs with complete bipartite induced minors Chudnovsky, Maria Hatzel, Meike Korhonen, Tuukka Trotignon, Nicolas Wiederrecht, Sebastian Combinatorics Discrete Mathematics 05C75, 05C85 G.2.2 We prove that if a graph contains the complete bipartite graph $K_{134, 12}$ as an induced minor, then it contains a cycle of length at most~12 or a theta as an induced subgraph. With a longer and more technical proof, we prove that if a graph contains $K_{3, 4}$ as an induced minor, then it contains a triangle or a theta as an induced subgraph. Here, a \emph{theta} is a graph made of three internally vertex-disjoint chordless paths $P_1 = a \dots b$, $P_2 = a \dots b$, $P_3 = a \dots b$, each of length at least two, such that no edges exist between the paths except the three edges incident to $a$ and the three edges incident to $b$. A consequence is that excluding a grid and a complete bipartite graph as induced minors is not enough to guarantee a bounded tree-independence number, or even that the treewidth is bounded by a function of the size of the maximum clique, because the existence of graphs with large treewidth that contain no triangles or thetas as induced subgraphs is already known (the so-called layered wheels). |
| title | Unavoidable induced subgraphs in graphs with complete bipartite induced minors |
| topic | Combinatorics Discrete Mathematics 05C75, 05C85 G.2.2 |
| url | https://arxiv.org/abs/2405.01879 |