2012/12/30 by Allan Lo, Lo, Allan
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO
paper · pdf · doi:10.48550/arxiv.1212.6736
18 pages, minor revision. Now accepted for publication in Combinatorica
arxiv created 2014/10/14 · arxiv updated 2014/10/15
Let Knc be an edge-coloured complete graph on n vertices. Let Δ\rm mon(Knc) denote the largest number of edges of the same colour incident with a vertex of Knc. A properly coloured cycle is a cycle such that no two adjacent edges have the same colour. In 1976, Bollobás and Erdős conjectured that every Knc with Δ\rm mon(Knc) < \lfloor n/2 \rfloor contains a properly coloured Hamiltonian cycle. In this paper, we show that for any ε > 0 , there exists an integer n0 such that every Knc with Δ\rm mon(Knc) < (1/2 - ε) n and n ≥ n0 contains a properly coloured Hamiltonian cycle. This improves a result of Alon and Gutin. Hence, the conjecture of Bollobás and Erdős is true asymptotically.