Bounds and complexity results of rainbow vertex-disconnection colorings

A subset $Y\subseteq V(G)$ in a vertex-colored graph $G$ is termed rainbow when vertices in $Y$ receive distinct colors from each other. For each pair of vertices $w_1,w_2\in V(G)$, if there exists $\mathcal{F}\subseteq V(G)$ satisfying $\mathcal{F}$ rainbow and $w_1,w_2$ disconnected in $G-\mathcal{F}$ for nonadjacent $w_1,w_2$; $\mathcal{F}+w_1$ or $\mathcal{F}+w_2$ rainbow and $w_1,w_2$ disconnected in $(G-w_1{w}_2)-\mathcal{F}$ for adjacent $w_1,w_2$, then $G$ is rainbow vertex-disconnected. The smallest number needed to color $G$ so that it is rainbow vertex-disconnected is known as the rainbow vertex-disconnection number of $G$, or $rvd(G)$. The RVD-Problem aims to determine whether $G$ has a rainbow vertex-disconnection coloring with $k$ colors given the graph $G$ and a positive integer $k$. In this paper, some bounds between $rvd(G)$ and different parameters, such as diameter, independence number, and so on, are obtained. Some results of rainbow vertex-disconnection numbers of three graph products are then obtained. Last, we demonstrate that there is a polynomial time approach that approximates $rvd(G)$ of split graph $G$ within a factor of $n^{2/3}$. We show RVD-Problem is $NP$-complete for induced $K_{1,t}$-free split graphs for $t\ge 4$ but polynomially solvable for $t\le 3$.