
arXiv: 1209.2981
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 $\mathrm{rc}(G)$ of the graph $G$. For any graph $G$, $\mathrm{rc}(G) \geqslant \mathrm{diam}(G)$. We will show that for the Erdős-Rényi random graph $\mathcal{G}(n,p)$ close to the diameter $2$ threshold, with high probability if $\mathrm{diam}(G)=2$ then $\mathrm{rc}(G)=2$. In fact, further strengthening this result, we will show that in the random graph process, with high probability the hitting times of diameter $2$ and of rainbow connection number $2$ coincide.
Coloring of graphs and hypergraphs, rainbow connection number, Distance in graphs, 05C80, Random graphs (graph-theoretic aspects), FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Paths and cycles, random graph process, random graph
Coloring of graphs and hypergraphs, rainbow connection number, Distance in graphs, 05C80, Random graphs (graph-theoretic aspects), FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Paths and cycles, random graph process, random graph
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 6 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
