Colorful monochromatic connectivity of random graphs

Abstract

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 $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ pairs of vertices appears as an edge with probability $p$ independently 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)$.

7 pages