Compatible Hamilton cycles in graphs with large minimum degree
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866917358093729792 |
|---|---|
| author | Behague, Natalie Di Braccio, Francesco Granet, Bertille Lo, Allan |
| author_facet | Behague, Natalie Di Braccio, Francesco Granet, Bertille Lo, Allan |
| contents | The renowned theorem of Dirac states that if $G$ is a graph with minimum degree at least $n/2$ then $G$ has a Hamilton cycle. A natural generalisation asks what properties of an edge-colouring of $G$ guarantee the existence of a properly edge-coloured Hamilton cycle in $G$. This concept can be further generalised as follows: an \emph{incompatibility system} for $G$ is a set~$\mathcal{F}$ of `forbidden' pairs of adjacent edges, that is, $\mathcal{F}\subseteq \{\{uv,vw\}\in \binom{E(G)}2\}$. A cycle in $G$ is then \emph{compatible} if no two of its edges form a pair in $\mathcal{F}$. The system $\mathcal{F}$ is called \emph{$μn$-bounded} if for all $v\in V(G)$ and $uv\in E(G)$, there are at most $μn$ pairs $\{uv,vw\}\in \mathcal{F}$. How small must $μ$ be to guarantee the existence of a compatible Hamilton cycle in $G$? Krivelevich, Lee and Sudakov showed that $μ=10^{-16}$ suffices (for $n$ large), while an example of Bollobás and Erdős shows that $μ\leq 1/4$ is necessary. We significantly reduce this gap for large graphs of minimum degree at least $(1/2+\varepsilon)n$, by showing that $μ=1/8$ suffices but $μ\leq 1/6$ is necessary for such graphs. In fact, we give more precise bounds which are functions of $δ(G)/n$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_21984 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Compatible Hamilton cycles in graphs with large minimum degree Behague, Natalie Di Braccio, Francesco Granet, Bertille Lo, Allan Combinatorics The renowned theorem of Dirac states that if $G$ is a graph with minimum degree at least $n/2$ then $G$ has a Hamilton cycle. A natural generalisation asks what properties of an edge-colouring of $G$ guarantee the existence of a properly edge-coloured Hamilton cycle in $G$. This concept can be further generalised as follows: an \emph{incompatibility system} for $G$ is a set~$\mathcal{F}$ of `forbidden' pairs of adjacent edges, that is, $\mathcal{F}\subseteq \{\{uv,vw\}\in \binom{E(G)}2\}$. A cycle in $G$ is then \emph{compatible} if no two of its edges form a pair in $\mathcal{F}$. The system $\mathcal{F}$ is called \emph{$μn$-bounded} if for all $v\in V(G)$ and $uv\in E(G)$, there are at most $μn$ pairs $\{uv,vw\}\in \mathcal{F}$. How small must $μ$ be to guarantee the existence of a compatible Hamilton cycle in $G$? Krivelevich, Lee and Sudakov showed that $μ=10^{-16}$ suffices (for $n$ large), while an example of Bollobás and Erdős shows that $μ\leq 1/4$ is necessary. We significantly reduce this gap for large graphs of minimum degree at least $(1/2+\varepsilon)n$, by showing that $μ=1/8$ suffices but $μ\leq 1/6$ is necessary for such graphs. In fact, we give more precise bounds which are functions of $δ(G)/n$. |
| title | Compatible Hamilton cycles in graphs with large minimum degree |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2603.21984 |