An edge-colored graph $G$ is rainbow connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connection number of a connected graph $G$, denoted by $rc(G)$, is the smallest number of colors that are needed in order to make $G$ rainbow connected. Following an idea of Caro et al., in this paper we also investigate the rainbow connection number of dense graphs. We show that for $k\geq 2$, if $G$ is a non-complete graph of order $n$ with minimum degree $\delta (G)\geq \frac{ n}{ 2}-1+log_{ k}{ n}$, or minimum degree-sum $\sigma_{ 2}(G)\geq n-2+2log_{ k}{ n}$, then $rc(G)\leq k$; if $G$ is a graph of order $n$ with diameter 2 and $\delta (G)\geq 2(1+log_{ \frac{ k^{ 2}}{ 3k-2}}{ k})log_{ k}{ n}$, then $rc(G)\leq k$. We also show that if $G$ is a non-complete bipartite graph of order $n$ and any two vertices in the same vertex class have at least $2log_{ \frac{ k^{ 2}}{ 3k-2}}{ k}log_{ k}{ n}$ common neighbors in the other class, then $rc(G)\leq k$.
Categories: math.CO