  A path in an edge-colored graph is said to be a rainbow path if no two edges
on the path have the same color. An edge-colored graph is (strongly) rainbow
connected if there exists a rainbow (geodesic) path between every pair of
vertices. The (strong) rainbow connection number of $G$, denoted by ($scr(G)$,
respectively) $rc(G)$, is the smallest number of colors that are needed in
order to make $G$ (strongly) rainbow connected. Though for a general graph $G$
it is NP-Complete to decide whether $rc(G)=2$, in this paper, we show that the
problem becomes easy when $G$ is a bipartite graph. Moreover, it is known that
deciding whether a given edge-colored (with an unbound number of colors) graph
is rainbow connected is NP-Complete. We will prove that it is still NP-Complete
even when the edge-colored graph is bipartite. We also show that a few NP-hard
problems on rainbow connection are indeed NP-Complete.

Computational Complexity;Combinatorics