Long properly coloured cycles in edge-coloured graphs


Abstract in English

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 $varepsilon >0$ and $n$ large, every edge-coloured graph $G$ with $delta^c(G) ge (1/2+varepsilon)n$ contains a properly coloured cycle of length at least $min{ n , lfloor 2 delta^c(G)/3 rfloor}$.

Download