Rainbow Hamilton cycles in random regular graphs

Svante Janson, Nicholas Wormald

Research output: Contribution to journalArticleResearchpeer-review

13 Citations (Scopus)

Abstract

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 & Algorithms
Volume30
Issue number1-2
DOIs
Publication statusPublished - Jan 2007
Externally publishedYes

Cite this