Note on two results on the rainbow connection number of graphs

Wei Li, Xueliang Li

Published 2011-10-23Version 1

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. Caro et al. showed an upper bound $rc(G)\leq n-\delta$ for a connected graph $G$ of order $n$ with minimum degree $\delta$ in "On rainbow connection, Electron. J. Combin. 15(2008), R57". Recently, Shiermeyer gave it a generalization that $rc(G)\leq n- \frac{\sigma_2} 2$ in "Bounds for the rainbow connection number of graphs, Discuss. Math Graph Theory 31(2011), 387--395", where $\sigma_2$ is the minimum degree-sum. The proofs of both results are almost the same, both fix the minimum degree $\delta$ and then use induction on $n$. This short note points out that this proof technique does not work rigorously. Fortunately, Caro et al's result is still true but under our improved proof. However, we do not know if Shiermeyer's result still hold.