Hostname: page-component-74656f9884-npj9w Total loading time: 0 Render date: 2026-11-08T23:04:46.269Z Has data issue: false hasContentIssue false
  • English
  • Français

Multi-Coloured Hamilton Cycles in Random Edge-Coloured Graphs

Published online by Cambridge University Press:  25 April 2002

COLIN COOPER  and
ALAN FRIEZE
COLIN COOPER
Affiliation:
Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh PA15213, USA (e-mail: alan@random.math.cmu.edu)
ALAN FRIEZE
Affiliation:
School of Mathematical and Computing Sciences, Goldsmiths College, University of London, London SE14 6NW, UK (e-mail: c.cooper@gold.ac.uk)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We define a space of random edge-coloured graphs [Gscr]n,m,κ which correspond naturally to edge κ-colourings of Gn,m. We show that there exist constants K0, K1 [les ] 21 such that, provided m [ges ] K0n log n and κ [ges ] K1n, then a random edge-coloured graph contains a multi-coloured Hamilton cycle with probability tending to 1 as the number of vertices n tends to infinity.

Information

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 11 , Issue 2 , March 2002 , pp. 129 - 133
Copyright
2002 Cambridge University Press