The complexity of determining the rainbow vertex-connection of a graph
A vertex-colored graph is rainbow vertex-connected if any two vertices are connected by a path whose internal vertices have distinct colors, which was introduced by Krivelevich and Yuster. The rainbow vertex-connection of a connected graph G, denoted by rvc(G), is the smallest number of colors that are needed in order to make G rainbow vertex-connected. In this paper, we study the complexity of determining the rainbow vertex-connection of a graph and prove that computing rvc(G) is NP-Hard. Moreover, we show that it is already NP-Complete to decide whether rvc(G) = 2. We also prove that the following problem is NP-Complete: given a vertex-colored graph G, check whether the given coloring makes G rainbow vertex-connected. (C) 2011 Elsevier B.V. All rights reserved.
rainbow vertex-connection coloring computational complexity