Nordhaus- gaddum-type bounds for the rainbow vertex-connection number of a graph - Chen, Lily; Li, Xueliang; Liu, Mengmeng (Utilitas Mathematica, 2011)
A vertex-colored graph G is rainbow vertex-connected if any pair of distinct vertices are connected by a path whose internal vertices have distinct colors. The rainbow vertex-connection number of G, denoted by rvc(G), is the minimum number of colors that are needed to make G rainbow vertex-connected. In this paper we give a Nordhaus-Gaddum-type result of the rainbow vertex-connection number. We prove that when G and Ḡ are both connected, then 2 < rvc(G) + rvc(Ḡ) ≤ n-1. Examples are given to show that both the upper bound and the lower bound are best possible for all n > 5.