Rainbow Vertex Connection Number of Dense and Sparse Graphs

Abstract

A vertex-colored graph \(G\) is rainbow connected, if any two vertices are connected by a path whose internal vertices have distinct colors. The rainbow vertex connection number of a connected graph \(G\), denoted \(\mathrm{rvc}(G)\), is the smallest number of colors that are needed in order to make \(G\) rainbow vertex connected. In this paper, we show that \(\mathrm{rvc}(G) \leq k\), if \(|E(G)| \geq \binom{n-k}{2} + k\), for \(k = 2, 3, n-4, n-5, n-6\). These bounds are sharp.