Rainbow Connection Number and Connectivity

The rainbow connection number, rc(G), of a connected graph G is the minimum number of colors needed to color its edges, so that every pair of vertices is connected by at least one path in which no two edges are colored the same. Our main result is that rc(G) <= inverted right perpendicularn/2inverted left perpendicular for any 2-connected graph with at least three vertices. We conjecture that rc(G) <= n/kappa + C for a kappa-connected graph G of order n, where C is a constant, and prove the conjecture for certain classes of graphs. We also prove that rc(G) < (2 + epsilon)n/kappa + 23/epsilon(2) for any epsilon > 0.