Induced subdivisions with pinned branch vertices
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866908301773504512 |
|---|---|
| author | Hajebi, Sepehr |
| author_facet | Hajebi, Sepehr |
| contents | We prove that for all $r\in \mathbb{N}\cup \{0\}$ and $s,t\in \mathbb{N}$, there exists $Ω=Ω(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 $(\leq 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 $(\leq 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2308_01502 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Induced subdivisions with pinned branch vertices Hajebi, Sepehr Combinatorics We prove that for all $r\in \mathbb{N}\cup \{0\}$ and $s,t\in \mathbb{N}$, there exists $Ω=Ω(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 $(\leq 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 $(\leq 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. |
| title | Induced subdivisions with pinned branch vertices |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2308.01502 |