Note on the complexity of deciding the rainbow connectedness for bipartite graphs
arXiv:1109.5534
Abstract
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 , denoted by (, respectively) , is the smallest number of colors that are needed in order to make (strongly) rainbow connected. Though for a general graph it is NP-Complete to decide whether , in this paper, we show that the problem becomes easy when 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.
6 pages