Long properly colored 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. Let ${\Delta }^{\mathrm{mon}}(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$ is a cycle (path) in which adjacent edges have distinct colors. B. Bollobás and P. Erdös (1976) proposed the following conjecture: if ${\Delta }^{\mathrm{mon}}(K_n^c)<\lfloor \frac{n}{2}\rfloor$, then $K_n^c$ contains a properly colored Hamiltonian cycle. Li, Wang and Zhou proved that if ${\Delta }^{\mathrm{mon}}(K_n^c)<\lfloor \frac{n}{2}\rfloor$, then $K_n^c$ contains a properly colored cycle of length at least $\lceil \frac{n+2}{3}\rceil +1$. In this paper, we improve the bound to $\lceil \frac{n}{2}\rceil +2$.

8 pages