More on the Colorful Monochromatic Connectivity.

An edge-coloring of a connected graph is a monochromatically-connecting coloring (MC-coloring, for short) if there is a monochromatic path joining any two vertices, which was introduced by Caro and Yuster. 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, in which case we simply let $$mc(G)=0$$ . In this paper, we characterize all connected graphs of size m with $$mc(G)=1, 2, 3, 4$$ , $$m-1$$ , $$m-2$$ and $$m-3$$ , respectively. We use G( n, p) to denote the Erdős-Rényi random graph model, in which each of the $$\left( {\begin{array}{c}n\\ 2\end{array}}\right) $$ pairs of vertices appears as an edge with probability p independent from other pairs. For any function f( n) satisfying $$1\le f(n)<\frac{1}{2}n(n-1)$$ , we show that if $$\ell n \log n\le f(n)<\frac{1}{2}n(n-1)$$ , where $$\ell \in \mathbb {R}^+$$ , then $$p=\frac{f(n)+n\log \log n}{n^2}$$ is a sharp threshold function for the property $$mc\left( G\left( n,p\right) \right) \ge f(n)$$ ; if $$f(n)=o(n\log n)$$ , then $$p=\frac{\log n}{n}$$ is a sharp threshold function for the property $$mc\left( G\left( n,p\right) \right) \ge f(n)$$ . [ABSTRACT FROM AUTHOR]