Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2022
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2212.02079 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910177997881344 |
|---|---|
| author | Karol, Nikolai |
| author_facet | Karol, Nikolai |
| contents | Let $G$ be a $3$-connected graph. A set $W \subset V(G)$ is called contractible if $G(W)$ is a connected graph and $G - W$ is a $2$-connected graph. In 1994, McCuaig and Ota conjectured that for any $k \in \mathbb{N}$ there exists $n \in \mathbb{N}$ such that any 3-connected graph $G$ with $v(G) \geqslant n$ has a $k$-vertex contractible set. It is proved that this holds if $k \geqslant 5$ and $δ(G) \geqslant \left[ \frac{2k + 1}{3} \right] + 2$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2212_02079 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Restriction on minimum degree in the contractible sets problem Karol, Nikolai Combinatorics 05C40 Let $G$ be a $3$-connected graph. A set $W \subset V(G)$ is called contractible if $G(W)$ is a connected graph and $G - W$ is a $2$-connected graph. In 1994, McCuaig and Ota conjectured that for any $k \in \mathbb{N}$ there exists $n \in \mathbb{N}$ such that any 3-connected graph $G$ with $v(G) \geqslant n$ has a $k$-vertex contractible set. It is proved that this holds if $k \geqslant 5$ and $δ(G) \geqslant \left[ \frac{2k + 1}{3} \right] + 2$. |
| title | Restriction on minimum degree in the contractible sets problem |
| topic | Combinatorics 05C40 |
| url | https://arxiv.org/abs/2212.02079 |