Further hardness results on the rainbow vertex-connection number of graphs

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, which was introduced by Krivelevich and Yuster. The rainbow vertex-connection number 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 a previous paper we showed that it is NP-Complete to decide whether a given graph G has rvc(G)=2. In this paper we show that for every integer k≥2, deciding whether rvc(G)≤k is NP-Hard. We also show that for any fixed integer k≥2, this problem belongs to NP-class, and so it becomes NP-Complete.