Long Alternating Cycles in Edge-Colored Complete Graphs

Abstract

Let $K_n^c$ denote a complete graph on n vertices whose edges are colored in an arbitrary way. And let $\Delta (K_n^c)$ denote the maximum number of edges of the same color incident with a vertex of $K_n^c$. A properly colored cycle (path) in $K_n^c$, that is, a cycle (path) in which adjacent edges have distinct colors is called an alternating cycle (path). Our note is inspired by the following conjecture by B. bollobás and P. Erdős(1976): If $\Delta(K_n^c)<\lfloor n/2\rfloor$, then $K_n^c$ contains an alternating Hamiltonian cycle. We prove that if $\Delta (K_n^c)< \lfloor n/2\rfloor$, then $K_n^c$ contains an alternating cycle with length at least $\lceil \frac{n+2}{3}\rceil+1$.