Premium
Properly colored hamilton cycles in edge‐colored complete graphs
Author(s) -
Alon N.,
Gutin G.
Publication year - 1997
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/(sici)1098-2418(199709)11:2<179::aid-rsa5>3.0.co;2-p
Subject(s) - colored , combinatorics , vertex (graph theory) , mathematics , graph , hamiltonian path , multiple edges , complete graph , enhanced data rates for gsm evolution , discrete mathematics , computer science , artificial intelligence , materials science , composite material
It is shown that, for ϵ>0 and n > n 0 (ϵ), any complete graph K on n vertices whose edges are colored so that no vertex is incident with more than (1‐1/\sqrt2‐\epsilon)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. © 1997 John Wiley & Sons, Inc. Random Struct. Alg. , 11 , 179–186 (1997)