Properly colored Hamilton cycles in edge-colored complete graphs

N. Alon, G. Gutin

Research output: Contribution to journalArticlepeer-review

37 Scopus citations

Abstract

It is shown that, for ∈ > 0 and n > n0(∈), any complete graph K on n vertices whose edges are colored so that no vertex is incident with more than (1 - 1 / √2 - ∈)n edges of the same color contains a Hamilton cycle in which adjacent edges have distinct colors. Moreover, for every k between 3 and n any such K contains a cycle of length k in which adjacent edges have distinct colors.

Original languageEnglish (US)
Pages (from-to)179-186
Number of pages8
JournalRandom Structures and Algorithms
Volume11
Issue number2
DOIs
StatePublished - Sep 1997

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)
  • Computer Graphics and Computer-Aided Design
  • Applied Mathematics

Keywords

  • Alternating cycles
  • Directed graphs
  • Edge-colored graphs
  • Hamilton cycles

Fingerprint Dive into the research topics of 'Properly colored Hamilton cycles in edge-colored complete graphs'. Together they form a unique fingerprint.

Cite this