Cycles of given color patterns. (English) Zbl 0839.05056

Manoussakis, Y.; Spyratos, M.; Tuza, Zsolt

J. Graph Theory 21, No. 2, 153-162 (1996).

A 2-edge-colored complete graph \(K^c_n\) is a complete graph \(K_n\) with edges colored in colors 1 and 2. An \((s, t)\)-cycle in \(K^c_n\) is a cycle of length \(s+ t\), in which \(s\) consecutive edges are in one color and the remaining \(t\) edges are in the other color. This paper gives a characterization for the existence of \((s, t)\)-cycles in \(K^c_n\) and studies all possible \((s, t)\)-cycles of length 4 and shows that \(K^c_n\) contains an \((s, t)\)-Hamiltonian cycle unless it is isomorphic to a specified graph. This extends a result of A. Gyárfás.

Reviewer: Ma Zhongfan (Beijing)

MSC:

05C38	Paths and cycles
05C15	Coloring of graphs and hypergraphs
05C45	Eulerian and Hamiltonian graphs

Keywords:

2-edge-colored complete graph; \((s, t)\)-cycle; color