2025/06/04 by Chen, Wenchong, Cheng, Xinbu, Yan, Zhifei · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2506.04189
Given a graph G and an r-edge-colouring χ on E(G), a Hamilton cycle H⊂ G is said to have t colour-bias if H contains n/r+t edges of the same colour in χ. Freschi, Hyde, Lada and Treglown showed every r-coloured graph G on n vertices with δ(G)≥(r+1)n/2r+t contains a Hamilton cycle H with Ω(t) colour-bias, generalizing a result of Balogh, Csaba, Jing and Pluhár. In 2022, Gishboliner, Krivelevich and Michaeli proved that the random graph G(n,m) with m≥(1/2+ε)nlog n typically admits an Ω(n) colour biased Hamilton cycle in any r-colouring. In this paper, we investigate colour-biased Hamilton cycles in randomly perturbed graphs. We show that for every α>0, adding m=O(n) random edges to a graph Gα with δ(Gα)≥ αn typically ensures a Hamilton cycle with Ω(n) colour bias in any r-colouring of Gα∪ G(n,m). Conversely, for certain Gα, reducing the number of random edges to m=o(n) may eliminate all colour biased Hamilton cycles of G(n,m)∪ G in a certain colouring. In contrast, at the critical endpoint α=(r+1)/2r, adding m random edges typically results in a Hamilton cycle with Ω(m) colour-bias for any 1≪ m≤ n.