Induced subdivisions with pinned branch vertices

Abstract

We prove that for all $r\in \mathbb{N}\cup \{0\}$ and $s,t\in \mathbb{N}$, there exists $\Omega =\Omega (r,s,t)\in \mathbb{N}$ with the following property. Let $G$ be a graph and let $H$ be a subgraph of $G$ isomorphic to a $(\le r)$-subdivision of $K_{\Omega }$. Then either $G$ contains $K_t$ or $K_{t,t}$ as an induced subgraph, or there is an induced subgraph $J$ of $G$ isomorphic to a proper $(\le r)$-subdivision of $K_s$ such that every branch vertex of $J$ is a branch vertex of $H$. This answers in the affirmative a question of Lozin and Razgon. In fact, we show that both the branch vertices and the paths corresponding to the subdivided edges between them can be preserved.

References in corpus (2)

• On polynomial degree-boundedness
• Induced subdivisions in $K_{s,s}$-free graphs with polynomial average degree

Cited by in corpus (2)

• Induced subgraphs and tree decompositions XVI. Complete bipartite induced minors
• Chordal graphs, even-hole-free graphs and sparse obstructions to bounded treewidth