Author
Heckel, A
Riordan, O
Journal title
Graphs and Combinatorics 32 (2016), Issue 1, pp 161-174
Last updated
2024-02-17T10:43:23.547+00:00
Abstract
We call an edge colouring of a graph G a rainbow colouring if every pair of
vertices is joined by a rainbow path, i.e., a path where no two edges have the
same colour. The minimum number of colours required for a rainbow colouring of
the edges of G is called the rainbow connection number (or rainbow
connectivity) rc(G) of G. We investigate sharp thresholds in the
Erd\H{o}s-R\'enyi random graph for the property "rc(G) <= r" where r is a fixed
integer. It is known that for r=2, rainbow connection number 2 and diameter 2
happen essentially at the same time in random graphs. For r >= 3, we conjecture
that this is not the case, propose an alternative threshold, and prove that
this is an upper bound for the threshold for rainbow connection number r.
Symplectic ID
416229
Download URL
http://arxiv.org/abs/1307.7747v1
Favourite
Off
Publication type
Journal Article
Publication date
29 Jul 2013
Please contact us with feedback and comments about this page. Created on 08 Aug 2013 - 17:58.