2013/11/10 by Dudek, Andrzej, Frieze, Alan, Tsourakakis, Charalampos
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1311.2299
An edge colored graph G is rainbow edge connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connection of a connected graph G, denoted by rc(G), is the smallest number of colors that are needed in order to make G rainbow connected. In this work we study the rainbow connection of the random r-regular graph G=G(n,r) of order n, where r≥ 4 is a constant. We prove that with probability tending to one as n goes to infinity the rainbow connection of G satisfies rc(G)=O(log n), which is best possible up to a hidden constant.