Properly coloured Hamiltonian cycles in edge-coloured complete graphs (Q1677578): Difference between revisions

\textit{B. Bollobás} and \textit{P. Erdős} [Isr. J. Math. 23, 126--131 (1976; Zbl 0325.05114)] conjectured, that if the edges of the complete \(n\)-graph \(K_{n}\) are coloured such that the number of mono-chromatic edges at each vertex is strictly less than the integer part of \(n/2\) then there exists a properly coloured Hamiltonian cycle in \(K_{n}\). They proved this with \(n/2\) replaced by \(n/69\), answering a question posed by \textit{D. E. Daykin} [J. Comb. Theory, Ser. B 20, 149--152 (1976; Zbl 0316.05106)]. The present paper contains the important result that the conjecture of Erdős and Bollobás is true assymptotically, namely for \(n/2\) replaced by \((1/2 - \varepsilon)n\) and \(n\) large enough.