AntiRamsey graphs
Search
Subjects
 All (170)
 Ramsey Theory (40)
 Extremal Graph Theory (40)
 Coloring, Packing, and Covering (25)
 Random Graphs and Graph Enumeration (16)
 Hypergraphs (35)
 Infinite Graphs (14)
About Erdös
About This Site
A class of problems on antiRamsey 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 noncomplete bipartite graph \( H\) [3]. However, the problem still remains open for complete bipartite graphs including \( C_4\) and stars as well as nonbipartite graphs.
Bibliography  

1  S. Burr, P. Erdös, R. L. Graham and V. T. Sós, Maximal antiRamsey graphs and the strong chromatic number, J. Graph Theory 13 (1989), 263282. 
2  S. Burr, P. Erdös, P. Frankl, R. L. Graham, V. Sós,
Further results on maximal antiRamsey graphs, Graph theory, combinatorics and applications, Vol. 1 (Kalamazoo, MI,
1988), WileyIntersci. Publ., pp. 193206, Wiley, New York, 1991.

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