Induced subdivisions with pinned branch vertices

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 K t or K t , t as an induced subgraph, or there is an induced subgraph J of G isomorphic to a proper ( ≤ 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.

Authors

Institutions

Publication Details

Journal
European Journal of Combinatorics
Published
2024-09-23
DOI
https://doi.org/10.1016/j.ejc.2024.104072
Citations
2
Primary Topic
Advanced Graph Theory Research
Type
article
Field-Weighted Citation Impact
0.72

Funders

Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
article

Induced subdivisions with pinned branch vertices

Sepehr Hajebi
2 citations
European Journal of Combinatorics
Advanced Graph Theory Research
0.72
article

Induced subdivisions with pinned branch vertices

Sepehr Hajebi
article en
2 citations

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 K t or K t , t as an induced subgraph, or there is an induced subgraph J of G isomorphic to a proper ( ≤ 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.

European Journal of CombinatoricsVol. 124
University of Waterloo (CA)
Government of Ontario, Natural Sciences and Engineering Research Council of Canada
Openalex Percentile: Top 26%
Advanced Graph Theory Research
0.72
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.