The Hitting Time of Rainbow Connection Number Two

Abstract

In a graph $G$ with a given edge colouring, a rainbow path is a path all of whose edges have distinct colours. The minimum number of colours required to colour the edges of $G$ so that every pair of vertices is joined by at least one rainbow path is called the rainbow connection number $\mathrm{rc}(G)$ of the graph $G$. For any graph $G$, $\mathrm{rc}(G) \geqslant \mathrm{diam}(G)$. We will show that for the Erdős-Rényi random graph $\mathcal{G}(n,p)$ close to the diameter $2$ threshold, with high probability if $\mathrm{diam}(G)=2$ then $\mathrm{rc}(G)=2$. In fact, further strengthening this result, we will show that in the random graph process, with high probability the hitting times of diameter $2$ and of rainbow connection number $2$ coincide.