Proper connection number of random graphs

Abstract

A path in an edge-colored graph is called a proper path if no two adjacent edges of the path are colored the same. For a connected graph $G$, the proper connection number $pc(G)$ of $G$ is defined as the minimum number of colors needed to color its edges, so that every pair of distinct vertices of $G$ is connected by at least one proper path in $G$. In this paper, we show that almost all graphs have the proper 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$, $pc(G(n,p))\le 2$ if $p\ge \frac{\log n+\alpha (n)}{n}$, where $\alpha (n)\to \infty$.

13 pages