Conflict-free connection number of random graphs

Abstract

An edge-colored graph $G$ is conflict-free connected if any two of its vertices are connected by a path which contains a color used on exactly one of its edges. The conflict-free connection number of a connected graph $G$, denoted by $cfc(G)$, is the smallest number of colors needed in order to make $G$ conflict-free connected. In this paper, we show that almost all graphs have the conflict-free connection number 2. More precisely, let $G(n,p)$ 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$ independent from other pairs. We prove that for sufficiently large $n$, $cfc(G(n,p))\le 2$ if $p\ge \frac{\log n+\alpha (n)}{n}$, where $\alpha (n)\to \infty$. This means that as soon as $G(n,p)$ becomes connected with high probability, $cfc(G(n,p))\le 2$.

13 pages