-
Annika Heckel
-
Oliver Riordan
Keywords:
random graph, rainbow connection number, random graph process
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 rc(G) of the graph G. For any graph G, rc(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.