Los puntos clave no están disponibles para este artículo en este momento.
We prove that if a graph contains the complete bipartite graph K₁₃₄, ₁₂ 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₃, ₄ as an induced minor, then it contains a triangle or a theta as an induced subgraph. Here, a theta is a graph made of three internally vertex-disjoint chordless paths P₁ = a b, P₂ = a b, P₃ = a 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).
Chudnovsky et al. (Fri,) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: