Anti-Ramsey Numbers for Small Complete Bipartite Graphs

Abstract

Given two graphs $G$ and $H\subseteq G$, we consider edge-colorings of $G$ in which every copy of $H$ has at least two edges of the same color. Let $f(G,H)$ be the maximum number of colors used in such a coloring of $E(G)$. Erdős, Simonovits, and Sós determined the asymptotic behavior of $f$ when $G=K_n$, and $H$ contains no edge $e$ with $\chi (H–e)\le 2$. We study the function $f(G,H)$ when $G=K_n$, or $K_{m,n}$, and $H$ is $K_{2,t}$.