  Let $G$ be a nontrivial connected and vertex-colored graph. A vertex subset
$X$ is called rainbow if any two vertices in $X$ have distinct colors. The
graph $G$ is called \emph{rainbow vertex-disconnected} if for any two vertices
$x$ and $y$ of $G$, there exists a vertex subset $S$ such that when $x$ and $y$
are nonadjacent, $S$ is rainbow and $x$ and $y$ belong to different components
of $G-S$; whereas when $x$ and $y$ are adjacent, $S+x$ or $S+y$ is rainbow and
$x$ and $y$ belong to different components of $(G-xy)-S$. For a connected graph
$G$, the \emph{rainbow vertex-disconnection number} of $G$, $rvd(G)$, is the
minimum number of colors that are needed to make $G$ rainbow
vertex-disconnected.
  In this paper, we prove for any $K_4$-minor free graph, $rvd(G)\leq
\Delta(G)$ and the bound is sharp. We show it is $NP$-complete to determine the
rainbow vertex-disconnection number for bipartite graphs and split graphs.
Moreover, we show for every $\epsilon>0$, it is impossible to efficiently
approximate the rainbow vertex-disconnection number of any bipartite graph and
split graph within a factor of $n^{\frac{1}{3}-\epsilon}$ unless $ZPP=NP$.
