On Lengths of Rainbow Cycles

Boris Alexeev

Abstract


We prove several results regarding edge-colored complete graphs and rainbow cycles, cycles with no color appearing on more than one edge. We settle a question posed by Ball, Pultr and Vojtěchovský by showing that if such a coloring does not contain a rainbow cycle of length $n$, where $n$ is odd, then it also does not contain a rainbow cycle of length $m$ for all $m$ greater than $2n^2$. In addition, we present two examples which demonstrate that a similar result does not hold for even $n$. Finally, we state several open problems in the area.


Full Text: PDF