  For a connected graph $G$, the \emph{rainbow connection number $rc(G)$} of a
graph $G$ was introduced by Chartrand et al. In "Chakraborty et al., Hardness
and algorithms for rainbow connection, J. Combin. Optim. 21(2011), 330--347",
Chakraborty et al. proved that for a graph $G$ with diameter 2, to determine
$rc(G)$ is NP-Complete, and they left 4 open questions at the end, the last one
of which is the following: Suppose that we are given a graph $G$ for which we
are told that $rc(G)=2$. Can we rainbow-color it in polynomial time with $o(n)$
colors ? In this paper, we settle down this question by showing a stronger
result that for any graph $G$ with $rc(G)=2$, we can rainbow-color $G$ in
polynomial time by at most 5 colors.

Combinatorics