Back to Search Start Over

Colour-biased Hamilton cycles in random graphs

Authors :
Gishboliner, Lior
Krivelevich, Michael
Michaeli, Peleg
Publication Year :
2020

Abstract

We prove that a random graph $G(n,p)$, with $p$ above the Hamiltonicity threshold, is typically such that for any $r$-colouring of its edges there exists a Hamilton cycle with at least $(2/(r+ 1)-o(1))n$ edges of the same colour. This estimate is asymptotically optimal.<br />Comment: 20 pages, minor corrections

Subjects

Subjects :
Mathematics - Combinatorics

Details

Database :
arXiv
Publication Type :
Report
Accession number :
edsarx.2007.12111
Document Type :
Working Paper