
Xueliang Li

Sujuan Liu

L. Sunil Chandran

Rogers Mathew

Deepak Rajendraprasad
Abstract
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)\leq \lceil\frac{n}{2}\rceil$ for any 2connected graph with at least three vertices. We conjecture that $rc(G)\leq 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)\leq(2+\varepsilon)n/\kappa+23/\varepsilon^2$ for any $\varepsilon>0$.