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_1w_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\geq 4 $ but polynomially solvable for $ t\leq 3 $.