Color‐biased Hamilton cycles in random graphs. Issue 3 (21st August 2021) - Gishboliner, Lior; Krivelevich, Michael; Michaeli, Peleg
Abstract: We prove that a random graph G ( n, p ), with p above the Hamiltonicity threshold, is typically such that for any r ‐coloring of its edges there exists a Hamilton cycle with at least ( 2 / ( r + 1 ) − o ( 1 ) ) n edges of the same color. This estimate is asymptotically optimal.