Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2502.04726 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866917000365735936 |
|---|---|
| author | Dvořák, Zdeněk Martins, Beatriz Thomassé, Stéphan Trotignon, Nicolas |
| author_facet | Dvořák, Zdeněk Martins, Beatriz Thomassé, Stéphan Trotignon, Nicolas |
| contents | In 1980, Gupta, Kahn and Robertson proved that every graph $G$ with minimum degree at least $k\geq 2$ contains a cycle $C$ containing at least $k+1$ vertices each having at least $k$ neighbors in $C$ (so $C$ has at least $\frac{(k+1)(k-2)}{2}$ chords). In this work, we go further by showing that some of its edges can be contracted to obtain a graph with high minimum degree (we call such a minor of $C$ a \emph{cyclic minor}). We then investigate further cycles having cliques as cyclic minors, and show that minimum degree at least $O(k^2)$ guarantees a cyclic $K_k$-minor. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_04726 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Lollipops, dense cycles and chords Dvořák, Zdeněk Martins, Beatriz Thomassé, Stéphan Trotignon, Nicolas Combinatorics 05C38 G.2.2 In 1980, Gupta, Kahn and Robertson proved that every graph $G$ with minimum degree at least $k\geq 2$ contains a cycle $C$ containing at least $k+1$ vertices each having at least $k$ neighbors in $C$ (so $C$ has at least $\frac{(k+1)(k-2)}{2}$ chords). In this work, we go further by showing that some of its edges can be contracted to obtain a graph with high minimum degree (we call such a minor of $C$ a \emph{cyclic minor}). We then investigate further cycles having cliques as cyclic minors, and show that minimum degree at least $O(k^2)$ guarantees a cyclic $K_k$-minor. |
| title | Lollipops, dense cycles and chords |
| topic | Combinatorics 05C38 G.2.2 |
| url | https://arxiv.org/abs/2502.04726 |