Abstract
We prove that for all r∈N∪{0} and s,t∈N, there exists Ω=Ω(r,s,t)∈N with the following property. Let G be a graph and let H be a subgraph of G isomorphic to a (≤r)-subdivision of KΩ. Then either G contains Kt or Kt,t as an induced subgraph, or there is an induced subgraph J of G isomorphic to a proper (≤r)-subdivision of Ks 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.
| Original language | English (US) |
|---|---|
| Article number | 104072 |
| Journal | European Journal of Combinatorics |
| Volume | 124 |
| DOIs | |
| State | Published - Feb 2025 |
| Externally published | Yes |
All Science Journal Classification (ASJC) codes
- Discrete Mathematics and Combinatorics