2011/01/17 by Lily Chen, Xueliang Li, Chen, Lily +3 · 1 citation
Computer Science · Mathematics · #05C15 #05C40 #68Q25 #68R10 #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1101.3126
openalex publication_date 2011/01/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A vertex-colored graph is \it 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 \it 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 computational complexity of vertex-rainbow connection of graphs 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.