GRAPHS AND COMBINATORICS
© 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.).
Submitted to ORA: