Compatible Hamilton cycles in graphs with large minimum degree

Abstract

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 (\genfrac{}{}{0ex}{}{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{$\hat{I}¼n$-bounded} if for all $v\in V(G)$ and $uv\in E(G)$, there are at most $\hat{I}¼n$ pairs $\{uv,vw\}\in \mathcal{F}$. How small must $\hat{I}¼$ be to guarantee the existence of a compatible Hamilton cycle in $G$? Krivelevich, Lee and Sudakov showed that $\hat{I}¼=10^{-16}$ suffices (for $n$ large), while an example of Bollobás and Erdős shows that $\hat{I}¼\le 1/4$ is necessary. We significantly reduce this gap for large graphs of minimum degree at least $(1/2+\epsilon )n$, by showing that $\hat{I}¼=1/8$ suffices but $\hat{I}¼\le 1/6$ is necessary for such graphs. In fact, we give more precise bounds which are functions of $\hat{I}´(G)/n$.

23 pages