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 $ disconnecte...
Saved in:
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
AIMS Press
2025-03-01
|
| Series: | AIMS Mathematics |
| Subjects: | |
| Online Access: | https://www.aimspress.com/article/doi/10.3934/math.2025272 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | 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 $. |
|---|---|
| ISSN: | 2473-6988 |