2014/12/31 by Ran Gu, Xueliang Li, Gu, Ran +3
Mathematics · #05C15 #05C40 #05C80 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C15 #msc:05C40 #msc:05C80
paper · pdf · doi:10.48550/arxiv.1501.00079
7 pages
arxiv created 2014/12/31 · arxiv updated 2015/01/05
An edge-coloring of a connected graph G is called a \it monochromatic connection coloring (MC-coloring, for short), introduced by Caro and Yuster, if there is a monochromatic path joining any two vertices of the graph G. Let mc(G) denote the maximum number of colors used in an MC-coloring of a graph G. Note that an MC-coloring does not exist if G is not connected, and in this case we simply let mc(G)=0. We use G(n,p) to denote the Erdös-Rényi random graph model, in which each of the \binomn2 pairs of vertices appears as an edge with probability p independently from other pairs. For any function f(n) satisfying 1≤ f(n)<(1)/(2)n(n-1), we show that if ℓ n log n≤ f(n)<(1)/(2)n(n-1) where ℓ∈ ℝ+, then p=(f(n)+nloglog n)/(n2) is a sharp threshold function for the property mc(G(n,p))≥ f(n); if f(n)=o(nlog n), then p=(log n)/(n) is a sharp threshold function for the property mc(G(n,p))≥ f(n).