Rainbow Hamilton cycles in random regular graphs

Svante Janson, Nicholas Wormald

Research output: Contribution to journalArticleResearchpeer-review

14 Citations (Scopus)


A rainbow subgraph of an edge-colored graph has all edges of distinct colors. A random d-regular graph with d even, and having edges colored randomly with d/2 of each of n colors, has a rainbow Hamilton cycle with probability tending to 1 as n → ∞, for fixed d ≥ 8.

Original languageEnglish
Pages (from-to)35-49
Number of pages15
JournalRandom Structures and Algorithms
Issue number1-2
Publication statusPublished - Jan 2007
Externally publishedYes

Cite this