A remark on Hamilton cycles with few colors

2017/06/15 by Balla, Igor, Pokrovskiy, Alexey, Sudakov, Benny
#05C45 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1706.04903

Abstract

Akbari, Etesami, Mahini, and Mahmoody conjectured that every proper edge colouring of K_n with n colours contains a Hamilton cycle with ≤ O(log n) colours. They proved that there is always a Hamilton cycle with ≤ 8√ n colours. In this note we improve this bound to O(log³ n).

Related

• Near rainbow Hamilton cycles in dense graphs
• Properly coloured Hamiltonian cycles in edge-coloured complete graphs
• Long rainbow cycles and Hamiltonian cycles using many colors in properly edge-colored complete graphs
• A note on colour-bias Hamilton cycles in dense graphs
• Proper Hamiltonian Cycles in Edge-Colored Multigraphs