The hitting time of rainbow connection number two

Journal article

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) \ge diam(G)$. We will show that for the Erd\H{o}s-R\'enyi random graph $G(n,p)$ close to the diameter 2 threshold, with high probability if $diam(G)=2$ then $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.

Authors: Heckel, A; Riordan, O

• Publication status: Published
• Journal: Electronic J. Combinatorics 19 (2012), Issue 4, P37
• Volume: 19
• Issue: 4
• Pages: P37-P37
• Publication date: 2012-09-13
• EISSN: 1077-8926
• ISSN: 1077-8926
• Language: English
• Keywords: 05C80; math.CO