# 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.