On the anti-Ramsey number of forests

Abstract

We call a subgraph of an edge-colored graph rainbow subgraph, if all of its edges have different colors. The anti-Ramsey number of a graph $G$ in a complete graph $K_n$, denoted by $ar(K_n,G)$, is the maximum number of colors in an edge-coloring of $K_n$ with no rainbow subgraph copy of $G$. In this paper, we determine the exact value of the anti-Ramsey number for star forests and the approximate value of the anti-Ramsey number for linear forests. Furthermore, we compute the exact value of $ar(K_n,2P_4)$ for $n\ge 8$ and $ar(K_n,S_{p,q})$ for large $n$, where $S_{p,q}$ is the double star with $p+q$ leaves.

18 pages, 1 figure