Back to Search
Start Over
Colour-biased Hamilton cycles in random graphs
- 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 :
- Mathematics - Combinatorics
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.2007.12111
- Document Type :
- Working Paper