On lengths of rainbow cycles

zbMATH Open1111.05032arXivmath/0507456MaRDI QIDQ870025FDOQ870025

Boris Alexeev

Publication date: 12 March 2007

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

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 Vojtv{e}chovsk'{y} 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.

Full work available at URL: https://arxiv.org/abs/math/0507456

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38)

Cited In (8)

• Title not available (Why is that?)
• Monochromatic and heterochromatic subgraphs in edge-colored graphs - A survey
• Periods in missing lengths of rainbow cycles
• Colored graphs without colorful cycles
• The hitting time of rainbow connection number two
• Rainbow Odd Cycles
• A decomposition of Gallai multigraphs
• Balanced edge-colorings avoiding rainbow cliques of size four

   Recommendations

• Title not available (Why is that?) 👍 👎
• On odd rainbow cycles in edge-colored graphs 👍 👎
• Note on rainbow cycles in edge-colored graphs 👍 👎
• Rainbow Odd Cycles 👍 👎
• Rainbow Turán problem for even cycles 👍 👎

This page was built for publication: On lengths of rainbow cycles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q870025)