PROPERLY COLORED HAMILTON CYCLES IN EDGE-COLORED COMPLETE GRAPHS

It is shown that, for epsilon > 0 and n > n(0)(epsilon), any complete graph K on n vertices whose edges are colored so that no vertex is inc ident with more than (1-1/root 2-epsilon)n edges of the same color con tains a Hamilton cycle in which adjacent edges have distinct colors. M oreover, for every k between 3 and n any such K contains a cycle of le ngth k in which adjacent edges have distinct colors. (C) 1997 John Wil ey & Sons, Inc.