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.

Review text

Summary: 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.

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)

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