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.
Classification :
05C15, 05C80, 05C38, 05C12
Mots-clés :
random graph, rainbow connection number, random graph process
Affiliations des auteurs :
Annika Heckel
1
;
Oliver Riordan
1
1
Mathematical Institute
University of Oxford
24-29 St Giles'
Oxford OX1 3LB
Annika Heckel; Oliver Riordan. The hitting time of rainbow connection number two. The electronic journal of combinatorics, Tome 19 (2012) no. 4. doi: 10.37236/2708
@article{10_37236_2708,
author = {Annika Heckel and Oliver Riordan},
title = {The hitting time of rainbow connection number two},
journal = {The electronic journal of combinatorics},
year = {2012},
volume = {19},
number = {4},
doi = {10.37236/2708},
zbl = {1266.05034},
url = {http://geodesic.mathdoc.fr/articles/10.37236/2708/}
}
TY - JOUR
AU - Annika Heckel
AU - Oliver Riordan
TI - The hitting time of rainbow connection number two
JO - The electronic journal of combinatorics
PY - 2012
VL - 19
IS - 4
UR - http://geodesic.mathdoc.fr/articles/10.37236/2708/
DO - 10.37236/2708
ID - 10_37236_2708
ER -
%0 Journal Article
%A Annika Heckel
%A Oliver Riordan
%T The hitting time of rainbow connection number two
%J The electronic journal of combinatorics
%D 2012
%V 19
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/2708/
%R 10.37236/2708
%F 10_37236_2708
