An edge coloring $c: E(G) \to [k]$ of a graph $G$ is called a rainbow if all of its edges are colored with different colors. An Anti-Ramsey number $\text{ar}(G,H)$ for an ordered pair of graphs $G$ and $H$ is the smallest number $r$ such that for every edge coloring $c$ of $G$ with exactly $r$ colors, there exists an $H$-subgraph of $G$ such that the coloring $c$ on $H$ is a rainbow.
We determine exact values of the anti-Ramsey numbers for some particular pairs of graphs. For example, we show that the exact value of the anti-Ramsey number $\text{ar}(K_n,P_4)$ for a pair of graphs $K_n$ and $P_4$ is equal to $4$ if $n=4$, and is equal to $2$ if $n \geq 5$. Even though the graphs $P_4$ and $C_3$ have the same number of edges, the anti-Ramsey numbers $\text{ar}(K_n,P_4)$ and $\text{ar}(K_n,C_3)$ differ significantly. This is because the anti-Ramsey number $\text{ar}(K_n,C_3)$ is equal to the number $n$ of vertices in $K_n$. We also determine the exact value of the anti-Ramsey number for a pair of hypercubes $Q_n$ and $Q_{n-1}$. It turns out that when $n=3,4$ or $5$, the anti-Ramsey number $\text{ar}(Q_n,Q_{n-1})$ is smaller than the number of edges in graph $Q_n$ by $3$, and in case when $n \geq 6$ it is smaller by $2$.
|
