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
- Sepehr Hajebi (ORCID: https://orcid.org/0000-0002-4551-7834)
Institutions
- University of Waterloo (CA)
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
- Government of Ontario
- Natural Sciences and Engineering Research Council of Canada