On a conjecture of erdöus, simonovits, and sós concerning anti‐Ramsey theorems

For n ≧ k ≧ 3, let f ( n,C k ) denote the maximum number m for which it is possible to color the edges of the complete graph K n with m colors in such a way that each k ‐cycle C k in K n has atleast two edges of the same color. Erdös, Simonovits, and Sós conjectured that for every fixed k ≧ 3, f(n , C k ) = n ( k –2/2 + 1/ k –1) + O (1), and proved it only for k = 3. It is shown that f(n, C 4 ) = n + [1/3 n ] – 1, and the conjecture thus proved for k = 4. Some upper bounds are also obtained for f ( n, C k ), k ≧ 5.