On rainbow connection (Q1010776)

Summary: An edge-colored graph \(G\) is rainbow connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connection number of a connected graph \(G\), denoted \(rc(G)\), is the smallest number of colors that are needed in order to make \(G\) rainbow connected. In this paper we prove several non-trivial upper bounds for \(rc(G)\), as well as determine sufficient conditions that guarantee \(rc(G)=2\). Among our results we prove that if \(G\) is a connected graph with \(n\) vertices and with minimum degree 3 then \(rc(G) < 5n/6\), and if the minimum degree is \(\delta\) then \(rc(G) \leq \frac{\ln \delta}{\delta}n(1+o_\delta(1))\). We also determine the threshold function for a random graph to have \(rc(G)=2\) and make several conjectures concerning the computational complexity of rainbow connection.