Rainbow Connection in Graphs with Minimum Degree Three

摘要

An edge-coloured graph G is rainbow connected if any two vertices are connected by a path whose edges have distinct colours. The rainbow connection number of a connected graph G, denoted rc(G), is the smallest number of colours that are needed in order to make G rainbow connected. In this paper we prove that rc(G) < (3n/4) for graphs with minimum degree three, which was conjectured by Caro et al. [Y. Caro, A. Lev, Y. Roditty, Z. Tuza, and R. Yuster, On rainbow connection, The Electronic Journal of Combinatorics 15 (2008), #57.]