TY - JOUR
T1 - Induced subdivisions with pinned branch vertices
AU - Hajebi, Sepehr
N1 - Publisher Copyright:
© 2024 The Author(s)
PY - 2025/2
Y1 - 2025/2
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85204357676&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85204357676&partnerID=8YFLogxK
U2 - 10.1016/j.ejc.2024.104072
DO - 10.1016/j.ejc.2024.104072
M3 - Article
AN - SCOPUS:85204357676
SN - 0195-6698
VL - 124
JO - European Journal of Combinatorics
JF - European Journal of Combinatorics
M1 - 104072
ER -