Rainbow Cycles in Cube Graphs

Jens-P. Bode1, Arnfried Kemnitz1, Sebastian Struckmann1
1Computational Mathematics Technische Universitat Braunschweig 38023 Braunschweig, Germany

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 \leq 4 \).