Long properly coloured cycles in edge-coloured graphs

Abstract

Let $G$ be an edge-coloured graph. The minimum colour degree ${\delta }^c(G)$ of $G$ is the largest integer $k$ such that, for every vertex $v$, there are at least $k$ distinct colours on edges incident to $v$. We say that $G$ is properly coloured if no two adjacent edges have the same colour. In this paper, we show that, for any $\epsilon >0$ and $n$ large, every edge-coloured graph $G$ with ${\delta }^c(G)\ge (1/2+\epsilon )n$ contains a properly coloured cycle of length at least $\min \{n,\lfloor 2{\delta }^c(G)/3\rfloor \}$.

22 pages, for publication in Journal of Graph Theory