Properly coloured Hamiltonian cycles in edge-coloured complete graphs

Let K^c _n be an edge-coloured complete graph on n vertices. Let Δ_mon(K^c _n) denote the largest number of edges of the same colour incident with a vertex of K^c _n. A properly coloured cycle is a cycle such that no two adjacent edges have the same colour. In 1976, BollobÁs and ErdŐs[6] conjectured that every K^c _n with Δ_mon(K^c _n)<⌊n/2⌋contains a properly coloured Hamiltonian cycle. In this paper, we show that for any ε>0, there exists an integer n₀ such that every K^c _n with Δ_mon(K^c _n)<(1/2–ε)n and n≥n₀ contains a properly coloured Hamiltonian cycle. This improves a result of Alon and Gutin [1]. Hence, the conjecture of BollobÁs and ErdŐs is true asymptotically.