Anti-Ramsey graphs

A class of problems on anti-Ramsey graphs (proposed by Burr, Erdös, Graham, and Sós [1])

For a graph \(G\), determin the least integer \(r=f(n,e,G)\) so that there is some graph \(H\) on \(n\) vertices and \(e\) edges which can be \(r\)-edge colored such that all edges of every copy of \(G\) in \(H\) have different colors.

It seems to be a difficult problem to get good bounds for \( f(n,e,G)\) for a general graph \( G\) (see [1]). Even for special cases, there are large gaps between known bounds. For example, it was shown in [1] [2] that \( f(n,e,C_5) \geq c n\) for \( e= (1/4+ \epsilon)n^2\) and \( f(n,e,C_5)= O(n^2/\log n)\) for \( e=(1/2-\epsilon)n^2\). Also, \( f(n,e,P_4) > c' n\) for \( e= \epsilon n^2\) and \( f(n,e,P_4) \leq n\) for \( n=n^2/\exp(c \sqrt{\log n})\).

In 2006, Sárközy and Selkow, using the Regularity Lemma, proved that for any \( \alpha > 0\), \( f(n,\alpha n^2,H)/n \to \infty\) as \( n \to \infty\) for any connected non-complete bipartite graph \( H\) [3]. However, the problem still remains open for complete bipartite graphs including \( C_4\) and stars as well as non-bipartite graphs.

Bibliography
1 S. Burr, P. Erdös, R. L. Graham and V. T. Sós, Maximal anti-Ramsey graphs and the strong chromatic number, J. Graph Theory 13 (1989), 263-282.

2 S. Burr, P. Erdös, P. Frankl, R. L. Graham, V. Sós, Further results on maximal anti-Ramsey graphs, Graph theory, combinatorics and applications, Vol. 1 (Kalamazoo, MI, 1988), Wiley-Intersci. Publ., pp. 193-206, Wiley, New York, 1991.

3 G. Sárközy and S. Selkow, On an Anti-Ramsey Problem of Burr, Erdös Graham, and T. Sós, J. Graph Theory, 52 (2006), 147-156.