On the threshold for rainbow connection number in random graphs

Author: 

Heckel, A
Riordan, O

Publication Date: 

January 2016

Journal: 

GRAPHS AND COMBINATORICS

Last Updated: 

2019-06-04T23:41:55.557+01:00

Issue: 

1

Volume: 

32

DOI: 

10.1007/s00373-015-1534-5

page: 

161-174

abstract: 

© 2015 Springer Japan We call an edge colouring of a graph (Formula presented.) 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 (Formula presented.) is called the rainbow connection number (or rainbow connectivity) (Formula presented.) of (Formula presented.). We investigate sharp thresholds in the Erdős–Rényi random graph for the property “(Formula presented.)” where (Formula presented.) is a fixed integer. It is known that for (Formula presented.), rainbow connection number (Formula presented.) and diameter (Formula presented.) happen essentially at the same time in random graphs. For (Formula presented.), 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 (Formula presented.).

Symplectic id: 

416229

Download URL: 

Submitted to ORA: 

Not Submitted

Publication Type: 

Journal Article