CYCLES OF GIVEN COLOR PATTERNS

In 2-edge-colored graphs, we define an (s, t)-cycle to be a cycle of l ength s + t, in which s consecutive edges are in one color and the rem aining t edges are in the other color. Here we investigate the existen ce of (s, t)-cycles, in a 2-edge-colored complete graph K-n(c) on n ve rtices. In particular, in the first result we give a complete n charac terization for the existence of (s, t)-cycles in K-n(c) with n relativ ely large with respect to max({s, t}). We also study cycles of length 4 for all possible values of s and t. Then, we show that K-n(c) contai ns an (s, t)-hamiltonian cycle unless it is isomorphic to a specified graph. This extends a result of A. Gyarfas [Journal of Graph Theory, 7 (1983), 131-135]. Finally, we give some sufficient conditions for the existence of (s, 1)-cycles, For All s is an element of {2, 3..., n - 2}. (C) 1996 John Wiley & Sons, Inc.