Cycles of given color patterns. (English) Zbl 0839.05056

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.


05C38 Paths and cycles
05C15 Coloring of graphs and hypergraphs
05C45 Eulerian and Hamiltonian graphs
Full Text: DOI