
arXiv: 2405.01879
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).
26 pages, 14 figures. Statement of Lemma 5.2 slightly modified
FOS: Computer and information sciences, Discrete Mathematics (cs.DM), Combinatorics, Discrete Mathematics, 05C75, 05C85, FOS: Mathematics, Induced minor, Induced subgraph, [MATH] Mathematics [math], Combinatorics (math.CO), G.2.2, [INFO] Computer Science [cs], Tree-independence number
FOS: Computer and information sciences, Discrete Mathematics (cs.DM), Combinatorics, Discrete Mathematics, 05C75, 05C85, FOS: Mathematics, Induced minor, Induced subgraph, [MATH] Mathematics [math], Combinatorics (math.CO), G.2.2, [INFO] Computer Science [cs], Tree-independence number
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
