On the threshold for rainbow connection number r in random graphs

Author: 

Heckel, A
Riordan, O

Publication Date: 

January 2016

Journal: 

Graphs and Combinatorics 32 (2016), Issue 1, pp 161-174

Last Updated: 

2020-06-18T13:50:39.61+01:00

Issue: 

1

Volume: 

32

DOI: 

10.1007/s00373-015-1534-5

page: 

161-174

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: 

Submitted to ORA: 

Not Submitted

Publication Type: 

Journal Article