14:30
Rainbow connectivity is a new concept for measuring the connectivity of a graph which was introduced in 2008 by Chartrand, Johns, McKeon and Zhang. 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) >= diam(G). We will discuss rainbow connectivity in the random graph setting and present the result that for random graphs, rainbow connectivity 2 happens essentially at the same time as diameter 2. In fact, in the random graph process, with high probability the hitting times of diameter 2 and of rainbow connection number 2 coincide