Rainbow Cycles in Cube Graphs

Abstract

A graph $G$ is called rainbow with respect to an edge coloring if no two edges of $G$ have the same color. Given a host graph $H$ and a guest graph $G\subseteq H$, an edge coloring of $H$ is called $G$-anti-Ramsey if no subgraph of $H$ isomorphic to $G$ is rainbow. The anti-Ramsey number $f(H,G)$ is the maximum number of colors for which there is a $G$-anti-Ramsey edge coloring of $H$. In this note, we consider cube graphs $Q_n$ as host graphs and cycles $C_k$ as guest graphs. We prove some general bounds for $f(Q_n,C_k)$ and give the exact values for $n\le 4$.