An edge-coloured version of Dirac's theorem

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 every edge-coloured graph $G$ with ${\delta }^c(G)\ge 2|G|/3$ contains a properly coloured $2$-factor. Furthermore, we show that for any $\epsilon >0$ there exists an integer $n_0$ such that every edge-coloured graph $G$ with $|G|=n\ge n_0$ and ${\delta }^c(G)\ge (2/3+\epsilon )n$ contains a properly coloured cycle of length $\ell$ for every $3\le \ell \le n$. This result is best possible in the sense that the statement is false for ${\delta }^c(G)<2n/3$.

Minor revision. Accepted for publication in SIAM Journal Discrete Mathematics

References in corpus (1)

• Properly coloured Hamiltonian cycles in edge-coloured complete graphs