Rainbow vertex-connection and forbidden subgraphs

Abstract

A path in a vertex-colored graph is called \emph{vertex-rainbow} if its internal vertices have pairwise distinct colors. A graph $G$ is \emph{rainbow vertex-connected} if for any two distinct vertices of $G$, there is a vertex-rainbow path connecting them. For a connected graph $G$, the \emph{rainbow vertex-connection number} of $G$, denoted by $rvc(G)$, is defined as the minimum number of colors that are required to make $G$ rainbow vertex-connected. In this paper, we find all the families $\mathcal{F}$ of connected graphs with $|\mathcal{F}|\in \{1,2\}$, for which there is a constant $k_{\mathcal{F}}$ such that, for every connected $\mathcal{F}$-free graph $G$, $rvc(G)\le diam(G)+k_{\mathcal{F}}$, where $diam(G)$ is the diameter of $G$.

arXiv comment11 pages