Anti-Ramsey properties of random graphs

作者：Bohman Tom^*; Frieze Alan; Pikhurko Oleg; Smyth Cliff

来源：Journal of Combinatorial Theory - Series B, 2010, 100(3): 299-312.

DOI：10.1016/j.jctb.2009.09.002

• Ramsey theory
• Random graphs

We call a coloring of the edge set of a graph G a b-bounded coloring if no color is used more than b times. We say that a subset of the edges of G is rainbow if each edge is of a different color. A graph has property A(b, H) if every b-bounded coloring of its edges has a rainbow copy of H. We estimate the threshold for the random graph G(n,p) to have property A(b, H).

• 出版日期2010-5