| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4626937 | Applied Mathematics and Computation | 2015 | 7 Pages |
A path in an edge-colored graph is said to be a rainbow path if no two edges on the path share 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)scr(G), respectively) rc(G)rc(G), is the smallest number of colors that are needed in order to make G (strongly) rainbow connected. A vertex-colored graph G is rainbow vertex-connected if any pair of vertices in G are connected by a path whose internal vertices have distinct colors. The rainbow vertex-connection number of a connected graph G , denoted by rvc(G)rvc(G), is the smallest number of colors that are needed in order to make G rainbow vertex-connected. Though for a general graph G it is NP-Complete to decide whether rc(G)=2rc(G)=2 (or rvc(G)=2rvc(G)=2), in this paper, we show that the problem becomes easy when G is a bipartite graph. Whereas deciding whether rc(G)=3rc(G)=3 (or rvc(G)=3rvc(G)=3) is still NP-Complete, even when G is a bipartite graph. Moreover, it is known that deciding whether a given edge(vertex)-colored (with an unbound number of colors) graph is rainbow (vertex-) connected is NP-Complete. We will prove that it is still NP-Complete even when the edge(vertex)-colored graph is bipartite. We also show that a few NP-hard problems on rainbow connection are indeed NP-Complete.
