Abstract:

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 $rc(G)$ of the graph $G$. For any graph $G$, $rc(G) \ge diam(G)$. We will show that for the Erd\H{o}s-R\'enyi random graph $G(n,p)$ close to the diameter 2 threshold, with high probability if $diam(G)=2$ then $...

Expand abstract

Collapse abstract

Publication status:

Published

Metrics

---