Near rainbow Hamilton cycles in dense graphs

2024/11/27 by Danni Peng, Peng, Danni, Zhifei Yan +1
Mathematics · Computer Science · #Limits and Structures in Graph Theory #Graph theory and applications #Advanced Graph Theory Research

paper · pdf · doi:10.48550/arxiv.2411.18743

Abstract

Finding near-rainbow Hamilton cycles in properly edge-coloured graphs was first studied by Andersen, who proved in 1989 that every proper edge colouring of the complete graph on n vertices contains a Hamilton cycle with at least n-√(2n) distinct colours. This result was improved to n-O(log² n) by Balogh and Molla in 2019. In this paper, we consider Anderson's problem for general graphs with a given minimum degree. We prove every globally n/8-bounded (i.e. every colour is assigned to at most n/8 edges) properly edge-coloured graph G with δ(G) ≥ (1/2+ε)n contains a Hamilton cycle with n-o(n) distinct colours. Moreover, we show that the constant 1/8 is best possible.

Related

• Long rainbow cycles and Hamiltonian cycles using many colors in properly edge-colored complete graphs
• A remark on Hamilton cycles with few colors
• Almost all optimally coloured complete graphs contain a rainbow Hamilton path
• Properly coloured Hamiltonian cycles in edge-coloured complete graphs
• A note on colour-bias Hamilton cycles in dense graphs