< prev | up | next >

PDF logo On lengths of rainbow cycles

by Boris Alexeev


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 this result does not hold for even \(n\). Finally, we state several open problems in the area.

Approximate citation

Boris Alexeev
On lengths of rainbow cycles
Electronic Journal of Combinatorics 13 (2006), no. 1, R105, 14 pp.

Useful links

PDF logoDirect PDF link
Journal icon Published journal version
arXiv icon arXiv online preprint server version
MathSciNet icon Math Reviews (MathSciNet) review
Google Scholar icon Google Scholar entry
BiBTeX icon Individual BiBTex entry
< prev | up | next >