@article{Weng2025, 
author = {Yindi Weng},
title = {Bounds and complexity results of rainbow vertex-disconnection colorings},
year = {2025},
journal = {AIMS Mathematics},
volume = {10},
number = {3},
pages = {5960-5970},
keywords = {rainbow vertex-disconnected, graph products, complexity, approximability},
url = {https://www.sciopen.com/article/10.3934/math.2025272},
doi = {10.3934/math.2025272},
abstract = {A subset    Y  ⊆  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    ∈  V  (  G  ), if there exists        F    ⊆  V  (  G  ) satisfying        F   rainbow and        w    1    ,      w    2   disconnected in    G  −      F   for nonadjacent        w    1    ,      w    2  ;        F    +      w    1   or        F    +      w    2   rainbow and        w    1    ,      w    2   disconnected in    (  G  −      w    1        w    2    )  −      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    r  v  d  (  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    r  v  d  (  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    r  v  d  (  G  ) of split graph    G within a factor of        n          2              /            3      . We show RVD-Problem is    N  P-complete for induced        K          1      ,      t      -free split graphs for    t  ≥  4 but polynomially solvable for    t  ≤  3.}
}