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) \leq 2\). We study the function \(f(G, H)\) when \(G = K_n\), or \(K_{m,n}\), and \(H\) is \(K_{2,t}\).