On lengths of rainbow cycles

MaRDI QIDQ870025zbMATH OpenFDO

Authors Boris Alexeev

Publication date 12 March 2007

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

Full work available at URL https://arxiv.org/abs/math/0507456, https://eudml.org/doc/127268, http://www.emis.de/journals/EJC/Volume_13/Abstracts/v13i1r105.html

IPFS 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)

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.

Recommendations

• Long rainbow cycles in proper edge-colorings of complete graphs
• 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

Cited in

(16)

• Periods in missing lengths of rainbow cycles
• Colored graphs without colorful cycles
• Complete graphs with no rainbow path
• scientific article; zbMATH DE number 5995288 (Why is no real title available?)
• Rainbow even cycles
• The hitting time of rainbow connection number two
• Color the cycles
• Short rainbow cycles in graphs and matroids
• Long rainbow paths and rainbow cycles in edge colored graphs. A survey
• A decomposition of Gallai multigraphs
• On rainbow trees and cycles
• On odd rainbow cycles in edge-colored graphs
• Balanced edge-colorings avoiding rainbow cliques of size four
• Rainbow Odd Cycles
• Monochromatic and heterochromatic subgraphs in edge-colored graphs - A survey
• Cycles avoiding a color in colorful graphs

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)