Sharp upper bound for the rainbow connection numbers of 2-connected graphs

Original · EN

An edge-colored graph G, where adjacent edges may be colored the same, is rainbow connected if any two vertices of G are connected by a path whose edges have distinct colors. The rainbow connection number rc(G) of a connected graph G is the smallest number of colors that are needed in order to make G rainbow connected. In this paper, we give a sharp upper bound that rc(G)≤/2 for any 2-connected graph G of order n, which improves the results of Caro et al. to best possible.