Hardness results for rainbow disconnection of graphs
share
Let G be a nontrivial connected, edge-colored graph. An edge-cut S of G is called a rainbow cut if no two edges in S are colored with a same color. An edge-coloring of G is a rainbow disconnection coloring if for every two distinct vertices s and t of G, there exists a rainbow cut S in G such that s and t belong to different components of G∖ S. For a connected graph G, the rainbow disconnection number of G, denoted by rd(G), is defined as the smallest number of colors such that G has a rainbow disconnection coloring by using this number of colors. In this paper, we show that for a connected graph G, computing rd(G) is NP-hard. In particular, it is already NP-complete to decide if rd(G)=3 for a connected cubic graph. Moreover, we prove that for a given edge-colored (with an unbounded number of colors) connected graph G it is NP-complete to decide whether G is rainbow disconnected.
READ FULL TEXT