Bounds and complexity results of rainbow vertex-disconnection colorings

1.   Introduction

In this paper, we consider simple, nontrivial connected and undirected graphs. Use $V(G)$ and $E(G)$ to respectively denote the vertex set and edge set of graph $G$. The notation $n = |V(G)|$ represents the $order$ of $G$. For $v\in V(G)$, its open neighborhood is $N_{G}(v) = \{u\in V(G) | uv\in E(G)\}$. The degree of $v$ is $d_G(v) = |N_{G}(v)|$. $N_{G}[v] = N_{G}(v)\cup \{v\}$ is the closed neighborhood of $v$. The symbols $\delta(G)$ and $\Delta(G)$ represent the minimum and maximum degree of $G$, respectively. Let $P_n$ be a path of order $n$. The $k$-cycle is a cycle with $k$ vertices. Considering any two vertices $u$ and $v$ of $G$, if $u$ is adjacent to $v$, for convenience, it is sometimes denoted by $u\sim v$; otherwise, $u\not\sim v$.

Chartrand et al. ^[4] extended the concept of rainbow connection to rainbow disconnection. For a graph $G$ with edge colored, $R\subseteq E(G)$, is an edge-cut if $G-R$ is not connected. Additionally, $R$ is a $u_1$-$u_2$ rainbow cut if $R$ is rainbow and $u_1, u_2$ are disconnected in $G-R$. If there is a $u_1$-$u_2$ rainbow cut for any $u_1, u_2\in G$, then $G$'s edge coloring is a rainbow disconnection coloring. Its rainbow disconnection number, represented by $rd(G)$, means the minimum number of colors that are necessary.

Based on the perspective of vertex-cut, Bai et al. ^[1] presented the rainbow vertex-disconnection coloring. It is applicable to frequency distribution and cargo circulation, in which different colors of the rainbow vertex-cut is used to feedback different frequencies or interception locations.

Let $w_1$ and $w_2$ be two vertices of a vertex-colored graph $G$. $\mathcal{F}\subseteq V(G)$ is a $w_1$-$w_2$ vertex-cut if $w_1, w_2$ are in distinct components of $G-\mathcal{F}$ for $w_1\not\sim w_2$ and in distinct components of $(G-w_1w_2)-\mathcal{F}$ for $w_1\sim w_2$. Then $\mathcal{F}$ is called rainbow if $\mathcal{F}$ has no two vertices with the same color. A $w_1$-$w_2$ rainbow vertex-cut of $G$, denoted by $\mathcal{F}_{G}(w_1, w_2)$, is a $w_1$-$w_2$ vertex-cut $\mathcal{F}$ such that if $w_1\not\sim w_2$, $\mathcal{F}$ is rainbow; if $w_1\sim w_2$, $\mathcal{F}+w_1$ or $\mathcal{F}+w_2$ is rainbow.

$G$ is rainbow vertex-disconnected when it contains a $w_1$-$w_2$ rainbow vertex-cut for any $w_1, w_2\in V(G)$. The corresponding vertex-coloring $c$ is a rainbow vertex-disconnection coloring (RVD-Coloring) of $G$. Its required minimum number of colors is called rainbow vertex-disconnection number, represented as $rvd(G)$. An $rvd$-coloring is an RVD-Coloring using $rvd(G)$ colors.

Furthermore, based on proper coloring and monochromatic coloring, proper (vertex-)disconnection coloring and monochromatic (vertex-)disconnection coloring were presented. For more details, refer to ^[2,6,9,10].

Bai et al. ^[1] studied the relations between $rvd(G)$ and connected subgraph, block, connectivity, upper connectivity, and girth, respectively. Li et al. ^[11] obtained $\delta(G)\leq rvd(G)\leq \chi_i(G)$, where $\chi_i(G)$ is the minimum number of colors needed to make the open neighborhood of each vertex rainbow in a vertex-coloring of $G$. So what are the relations between other parameters and $rvd(G)$?

Chen et al. ^[5] demonstrated that, even in graph $G$ having $\Delta(G) = 3$ or being bipartite, determining if a given vertex-colored graph $G$ is rainbow vertex-disconnected is $NP$-complete. Given a positive integer $k$ and a graph $G$, RVD-Problem aims to determine if $G$ has an RVD-Coloring using $k$ colors. The current author ^[14] proved RVD-Problem is $NP$-complete for bipartite graphs and split graphs. For every $\epsilon > 0$, it is impossible to 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$. So in this paper, we will focus on the approximate result of split graphs and the complexity of subclasses of split graphs.

The remainder of the paper is organized as follows. In Section 2, we investigate relations between different parameters and $rvd(G)$, such as diameter, edge connectivity, independence number, and so on. In Section 3, $rvd(G)$ of graph products such as Cartesian product, direct product, and lexicographic product is explored. In Section 4, the approximate result of split graph is given. We prove that for a split graph $G$, there exists a polynomial time algorithm that approximates $rvd(G)$ within a factor of $n^{2/3}$. We also show that RVD-Problem is $NP$-complete for induced $K_{1, t}$-free split graphs for $t\geq 4$ but polynomially solvable for $t\leq 3$.

2.   Some bounds

In this section, we will study the relation of rainbow vertex-disconnection number with various parameters. First, we will consider the diameter.

For $w_1, w_2\in V(G)$, we denote the distance of $w_1$ and $w_2$ in $G$ by $d_{G}(w_1, w_2)$. The maximum distance, $diam(G)$, between every two vertices of a graph $G$ is its diameter.

Theorem 2.1. For a graph $G$ with $diam(G) = d$, $rvd(G)\leq n-d+2$.

Proof. Suppose $u, v\in V(G)$ with $d_{G}(u, v) = d$. The shortest path of $u$ and $v$ is denoted by $P_{uv} = uv_{1}v_2\cdots v_{d-1}v$. For convenience, let $u = v_0$ and $v = v_d$. Next, define the following vertex-coloring $c$ of graph $G$. For vertices in $P_{uv}$, let $c(v_i) = r+1$ where $i\equiv r\ (\text{mod}\ 3)$. We color the remaining vertices of $G$ using different colors $4, 5, \cdots, n-d+2$. Let $w_1, w_2$ be any pair of vertices of $G$. Then $N_G(w_1)$ is rainbow. For if $w_1$ is adjacent to two vertices $v_p$ and $v_q$ ($p < q$) with the same color in $P_{uv}$, then the path $v_{0}v_1\cdots v_{p}w_1v_{q}v_{q+1}\cdots v_{d}$ is a path between $u$ and $v$ that is shorter than $P_{uv}$, a contradiction. So if $w_1\sim w_2$, $\mathcal{F}_G(w_1, w_2) = N_G(w_1)\setminus\{w_2\}$. If $w_1\not\sim w_2$, $\mathcal{F}_G(w_1, w_2) = N_G(w_1)$. Therefore, $c$ is an RVD-Coloring. Specifically, $rvd(G)\leq n-d+2$. □

The edge connectivity $\lambda(G)$ of graph $G$ is the minimum number of edges of $G$ whose removal results in a disconnected graph.

Theorem 2.2. Let $R$ be the minimum edge-cut of graph $G$ and $G_1, G_2$ be connected components of $G-R$. Then $rvd(G)\leq max\{rvd(G_i)|i\in[2]\}+2\lambda(G)$.

Proof. Let $s = max\{rvd(G_i)|i\in[2]\}$ and $c_i$ be an rvd-coloring on $G_i$, where $i\in [2]$. Use $V(R)$ to denote the endpoints of minimum edge-cut $R$. Based on $c_i$ ($i\in[2]$), we recolor $V(R)$ using new colors $s+1, s+2, \cdots, s+|V(R)|$. Denote the vertex-coloring of $G$ by $c$. Let $w, z\in V(G)$. Assume $w\in G_p$ and $z\in G_q$, where $p, q\in [2]$. If $p = q$, assuming that $\mathcal{F}_{G_p}(w, z) = S_p$ with the vertex-coloring $c_p$, then $\mathcal{F}_G(w, z) = S_p\cup V(R)\setminus \{w, z\}$ with the vertex-coloring $c$. If $p\neq q$, then $\mathcal{F}_G(w, z) = V(R)\setminus\{w, z\}$ with the vertex-coloring $c$. So $c$ is an RVD-Coloring of $G$. Thus, $rvd(G)\leq s+|V(R)|\leq max\{rvd(G_i)|i\in[2]\}+2\lambda(G)$. □

Lemma 2.3. ^[3] Every graph with average degree at least 2k, where k is a positive integer, has an induced subgraph with minimum degree at least k + 1.

Lemma 2.4. ^[1] If $G$ is a nontrivial connected graph and $H$ is a connected subgraph of $G$, then $rvd(H)\leq rvd(G)$.

For $w_1, w_2\in V(G)$, if $w_1\not\sim w_2$, the local connectivity $\kappa_G(w_1, w_2)$ represents the smallest number of vertices to make $w_1, w_2$ disconnected. If $w_1\sim w_2$, $\kappa_G(w_1, w_2) = \kappa_{G-w_1w_2}(w_1, w_2)+1$. The connectivity $\kappa(G)$ means the smallest number of vertices in $G$ that, when removed, yield a trivial or disconnected graph. The upper connectivity $\kappa^+(G)$ satisfies $\kappa^+(G) = \text{max}\{\kappa_G(w_1, w_2)|w_1, w_2\in V(G)\}$.

Lemma 2.5. ^[11] For a graph $G$ with $\Delta(G) = \Delta$, $\delta(G)\leq \kappa^+(G)\leq rvd(G)\leq \chi_i(G)\leq \Delta(\Delta-1)+1$.

Theorem 2.6. For a graph $G$ with order $n$ and size $m$, $rvd(G)\geq \lfloor{\frac{m}{n}}\rfloor+1$.

Proof. Suppose that the average degree of graph $G$ is $\bar{d}$. So $\bar{d} = \frac{2m}{n}\geq 2\lfloor{\frac{m}{n}}\rfloor$. By Lemma 2.3, there is an induced subgraph $H$ with $\delta(H)\geq \lfloor{\frac{m}{n}}\rfloor+1$. Therefore, $rvd(G)\geq rvd(H)\geq \delta(H)\geq \lfloor{\frac{m}{n}}\rfloor+1$ by Lemmas 2.4 and 2.5. □

For $S\subseteq V(G)$, if it contains no two adjacent vertices, $S$ is referred to as an independent set of $G$. Furthermore, when there is no independent set containing more vertices than $S$, $S$ is maximum. The independence number of $G$, indicated by $\alpha(G)$, is the number of vertices in a maximum independent set of $G$.

Lemma 2.7. ^[1] Let $G$ be a nontrivial connected graph. Then $rvd(G) = 1$ if and only if $G$ is a tree.

Theorem 2.8. For a graph $G$ of order $n$, $rvd(G)\geq \lceil\frac{n}{2\alpha(G)}\rceil$, and the bound is sharp.

Proof. Suppose that $rvd(G) = k$. Denote the color classes of graph $G$ by $V_1, V_2, \cdots, V_k$. Then each $V_i$ ($i\in[k]$) induces a tree or a forest by Lemma 2.7. Assume that $T_1, T_2, \cdots, T_\ell$ are the connected components of $V_i$. Since $T_j$ ($j\in [\ell]$) is bipartite, we have $\alpha(T_j)\geq \lceil\frac{|T_j|}{2}\rceil$ ($j\in [\ell]$). We obtain

Since there exists $V_s$ with $|V_{s}|\geq \lceil\frac{n}{k}\rceil$ ($s\in [k]$), we have $\alpha(G)\geq max_{i\in [k]}\alpha(V_i)\geq \alpha(V_s)\geq \lceil\frac{n}{2k}\rceil$. Let $G = P_n$. When $n$ is odd, we have $\alpha(P_n) = \frac{n+1}{2}$ and $rvd(P_n) = 1$. When $n$ is even, we have $\alpha(P_n) = \frac{n}{2}$ and $rvd(P_n) = 1$. So the bound is tight. □

A vertex-coloring of $G$ is proper if any two adjacent vertices receive different colors. The chromatic number of $G$ is the minimum number of colors such that $G$ has a proper coloring, denoted by $\chi(G)$. $G$ is $k$-chromatic if $\chi(G) = k$. If $\chi(H) < \chi(G)$ for every proper subgraph $H$ of $G$, $G$ is critical. A graph is $k$-critical if it is critical and $\chi(G) = k$.

Lemma 2.9. ^[7] A $k$-chromatic graph contains a $k$-critical subgraph.

Lemma 2.10. ^[7] Let $G$ be a connected $(k+1)$-critical graph. Then $\delta(G)\geq k$.

Lemma 2.11. ^[11] Let $G$ be a connected graph of order $n$ with minimum degree $\delta$. If $\delta\geq \frac{n+2}{2}$, then $rvd(G) = n$.

Theorem 2.12. For a graph $G$ of order $n$, if $\chi(G)\geq \frac{n+4}{2}$, then $rvd(G) = \chi_{i}(G) = n$.

Proof. Assume that $\chi(G) = k$. There exists a $k$-critical subgraph $H$ by Lemma 2.9. Then $\delta(G)\geq \delta(H)\geq k-1\geq \frac{n+4}{2}-1 = \frac{n+2}{2}$ by Lemma 2.10. According to Lemma 2.11 and 2.5, $rvd(G) = \chi_{i}(G) = n$. □

Next, we get Theorem 2.15 to show the gap of $rvd(G)$ and $\chi_i(G)$ arbitrarily large.

A block of a graph G is a maximal 2-connected subgraph of $G$.

Lemma 2.13. ^[1] Let $G$ be a nontrivial connected graph, and let $B$ be a block of $G$ such that $rvd(B)$ is maximum among all blocks of $G$. Then $rvd(G) = rvd(B)$.

Lemma 2.14. ^[1] Let $G = K_{n_{1}, n_{2}, \ldots, n_{k}}$ be a complete $k$-partite graph of order $n$, where $k\geq 2$, $1\leq n_{1}\leq n_{2} \leq\cdots \leq n_{k}$ and $n_{k}\geq 2$. Then

Theorem 2.15. For any positive integers $a$ and $b$ with $a\leq b$, there exists a connected graph such that $rvd(G) = a$ and $\chi_i(G) = b$.

Proof. If $a = b = 1$, $rvd(K_2) = \chi_i(K_2) = 1$. Consider that $b > a = 1$ or $b\geq a\geq 2$. Assume that $K_{2, a}$ is a complete bipartite graph with bipartition $(V_1, V_2)$, where $V_1 = \{x, y\}$ and $V_2 = \{v_1, v_2, \cdots, v_a\}$. Add $b-a$ pendant edges to $x$. The new graph from $K_{2, a}$ is denoted by $G$, where the set of new $b-a$ vertices is $V_3 = \{v_{a+1}, v_{a+2}, \cdots, v_b\}$. Then $rvd(G) = rvd(K_{2, a}) = a$ by Lemmas 2.13 and 2.14. Since $\Delta(G) = b$, we have $\chi_i(G)\geq b$. Now give a vertex-coloring $c$ on $G$. Assume $c(x) = 1$, $c(y) = 2$, and $c(v_i) = i$ for $i\in [b]$. Then for any vertex $v$ of $G$, $N_G(v)$ is rainbow. So $c$ is an injective coloring of $G$ and $\chi_i(G)\leq b$. □

A graph is minimally $k$-connected if it is $k$-connected, but omitting any of the edges, the resulting graph is no longer $k$-connected.

Lemma 2.16. ^[13] Let $G$ be a minimally $k$-connected graph of order $n$. If $n\geq 3k-2$, then $|E(G)|\leq k(n-k)$. Furthermore, if $n\geq 3k-1$, equality holds if and only if $G = K_{k, n-k}$.

Lemma 2.17. ^[1] For integers $k$ and $n$ with $1\leq k\leq n$, the minimum size of a connected graph $G$ of order $n\geq 4$ with rvd$(G) = k$ is

Theorem 2.18. Let $G$ be a minimally $2$-connected graph with order $n$. If $n\geq 4$, $rvd(G)\leq n-2$. Furthermore, $rvd(G) = n-2$ if and only if $G = K_{2, n-2}$.

Proof. By Lemma 2.16, we have $|E(G)|\leq 2n-4$. By Lemma 2.17, $rvd(G)\leq n-2$. If $n = 4$, $G$ is $K_{2, 2}$, and $rvd(G) = 2$. If $n\geq 5$, by Lemma 2.16, $rvd(G) = n-2$ if and only if $G = K_{2, n-2}$. □

A graph G is outerplanar if it has a planar embedding $\widetilde{G}$ in which all vertices lie on the boundary of its outer face.

Lemma 2.19. ^[3] Every simple 2-connected outerplanar graph other than $K_2$ has a vertex of degree two.

Theorem 2.20. For an outerplanar graph $G$, $rvd(G)\leq 4$.

Proof. By Lemma 2.7, consider that $G$ is not a tree. If $G$ is a triangle, then $rvd(G) = 2$. So consider graph $G$ with order $n\geq 4$. If there is a cut vertex in $G$, assuming that the $2$-connected subgraph of $G$ with maximum rainbow vertex-disconnection number is $G'$, we obtain $rvd(G) = rvd(G')$ by Lemma 2.13. So suppose that $G$ is $2$-connected. If there is an interior face with length more than $3$, then we add some edges to make each interior face a 3-cycle. The resulting graph is denoted by $H$.

Next, we prove there exists an RVD-Coloring $c_{H}$ of graph $H$: $V(H)\rightarrow [4]$, satisfying the vertex set of each $4$-cycle is rainbow. For simplicity, we say that each $4$-cycle is rainbow.

For $n = 4$, we have $H = K_4-e$ and it suffices to color each vertex using different color. Assume that for graphs of order $n$, the assertion is true. Then consider graph $H$ with order $n+1$. By Lemma 2.19, select a vertex $v$ with $d_H(v) = 2$. Let $N_{H}(v) = \{v_1, v_2\}$. Since $H$ is an outerplanar graph, $H$ is $K_{2, 3}$ minor-free. So let $N_{H}(v_1)\cap N_{H}(v_2) = \{v, v_3\}$. Since $H-v$ is $2$-connected, there is an RVD-Coloring $c_{H-v}$: $V(H-v)\rightarrow [4]$ such that each $4$-cycle is rainbow. By coloring the vertex $v$ using the color different from $c_{H-v}(v_1), c_{H-v}(v_2), c_{H-v}(v_3)$, we obtain a vertex-coloring $c_H$ of graph $H$. Obviously, the $4$-cycle $vv_1v_3v_2$ is rainbow.

Let $w, z\in V(H)$. If $w = v$ or $z = v$, then $\mathcal{F}_H(w, z) = \{v_1, v_2\}\setminus\{z\}$ or $\{v_1, v_2\}\setminus\{w\}$. If $\{w, z\} = \{v_1, v_2\}$, then $\mathcal{F}_H(w, z) = \{v, v_3\}$. Except for them, $\mathcal{F}_H(w, z) = \mathcal{F}_{H-v}(w, z)$. So $c_H$ is an RVD-Coloring of $H$ such that each $4$-cycle is rainbow. Thus, $rvd(G)\leq 4$ by Lemma 2.4. □

3.   Results of graph products

Next, we study rainbow vertex-disconnection numbers of three kinds of graph products. First, we give the definitions of three kinds of graph products as follows.

Give two internal disjoint graphs $G, H$. The graph with vertex set $V (G)\times V (H)$ is Cartesian product $G \Box H$, where $(u, x)\sim (v, y)$ in $G \Box H$ if and only if either $u = v$ and $xy \in E(H)$ or $uv\in E(G)$ and $x = y$.

The direct product $G\times H$ is the graph with vertex set $V(G)\times V(H)$, where $(u, x)\sim (v, y)$ if and only if both $uv\in E(G)$ and $xy\in E(H)$.

The lexicographic product $G\circ H$ is the graph with vertex set $V (G)\times V(H)$, where $(u, x)\sim (v, y)$ if and only if $uv\in E(G)$, or $u = v$ and $xy\in E(H)$.

The stacked book graph is defined as $B_{m, n}\cong S_{m}\Box P_n$, where $S_m$ is a star with order $m+1$, $m\geq 2$, and $n\geq 2$.

Theorem 3.1. $rvd(B_{m, n}) = m+1$.

Proof. Let $V(S_m) = \{s_i|i\in [m+1]\}$, where $d_{S_m}(s_1) = m$. Let $V(P_n) = \{p_j|j\in[n]\}$. For convenience, denote vertex $(s_i, p_j)$ in $B_{m, n}$ by $v_{ij}$. Since $\kappa_{B_{m, n}}(v_{11}, v_{12}) = m+1$, $rvd(B_{m, n})\geq m+1$. Give a vertex-coloring $c$ of $B_{m, n}$ using $m+1$ colors as follows. Let $c(v_{1j}) = m$ for $j\in [n]$. Let $c(v_{ij}) = \lceil{\frac{j}{2}}\rceil+i-1$ (mod $m$) for $i\geq 2$ and $i\in[m+1]$ and $j\in[n]$. Except for $v_{1j}$, the open neighborhood of each vertex of $B_{m, n}$ is rainbow. Consider any two vertices $v_{1j_1}$ and $v_{1j_2}$, where $j_1 < j_2$. If $j_1 = 1$, then $N_{B_{m, n}}(v_{1j_1})$ is rainbow; otherwise, $N_{B_{m, n}}(v_{1j_1})\setminus\{v_{1j_1-1}\}$ is rainbow. Thus, there exists $\mathcal{F}_{B_{m, n}}(v_{1j_1}, v_{1j_2})$. So $rvd(B_{m, n})\leq m+1$. □

Lemma 3.2. ^[1] Let $G$ be a nontrivial connected graph, and let $u$ and $v$ be two vertices of $G$ having at least two common neighbors. Then $u$ and $v$ receive different colors in any rvd-coloring of $G$.

Lemma 3.3. ^[1] Let $G$ be a nontrivial connected graph of order $n$. Then $rvd(G) = n$ if and only if any two vertices of $G$ have at least two common neighbors.

Theorem 3.4. For nontrivial connected graphs $G$ and $H$, $max\{\kappa^{+}(G)+\Delta(H), \kappa^{+}(H)+\Delta(G)\}\leq rvd(G \Box H)\leq |V(G)|\cdot |V(H)|$. Moreover, the upper and lower bounds are sharp.

Proof. The upper bound is obtained from $rvd(G\Box H)\leq |G\Box H| = |V(G)|\cdot |V(H)|$. According to Lemma 3.3, we have $rvd(K_{p}\Box K_{q}) = pq$, where $p\geq 4$ and $q\geq 4$. So the upper bound is sharp. Select row $i$ where each vertex has the maximum degree in the corresponding graph $G$. In the same row $i$, we select two vertices $x_{i, \ell}$ and $x_{i, s}$ satisfying $\kappa_{H}(x_{i, \ell}, x_{i, s}) = \kappa^{+}(H)$. Assume that $N_G(x_{i, \ell}) = \{x_{j_{1}, \ell}, x_{j_{2}, \ell}, \cdots, x_{j_{\Delta}, \ell}\}$. Consider the number of internally disjoint paths between $x_{i, \ell}$ and $x_{i, s}$. Since $H$ is connected, there is a path between $x_{j_{t}, \ell}$ and $x_{j_{t}, s}$ for $t\in \{1, 2, \cdots, \Delta\}$, say $P_{j_t}$, only through the vertices in row $j_t$. So paths $x_{i, \ell}P_{j_1}x_{i, s}$, $x_{i, \ell}P_{j_2}x_{i, s}, \cdots, x_{i, \ell}P_{j_\Delta}x_{i, s}$ are $\Delta(G)$ internally disjoint paths between $x_{i, \ell}$ and $x_{i, s}$. There exist at least $\kappa^{+}(H)$ internally disjoint paths in row $i$. Thus, $\kappa_{G\Box H}(x_{i, \ell}, x_{i, s})\geq \Delta(G)+\kappa^{+}(H)$. According to Lemma 2.5, $rvd(G\Box H)\geq \Delta(G)+\kappa^{+}(H)$. By symmetry, the lower bound is obtained. For a stacked book graph $B_{m, n}$, since $\Delta(S_m) = m$, $\kappa^{+}(P_n) = 1$, and $rvd(B_{m, n}) = m+1$ by Theorem 3.1, the lower bound is sharp. □

Theorem 3.5. For graphs $G, H$ with $\Delta(G)\geq 2$ and $\Delta(H)\geq 2$, $max\{\Delta(G), \Delta(H)\}\leq rvd(G\times H)\leq |V(H)||V(G)|$.

Proof. Denote each vertex of $G\times H$ by $(u, v)$, where $u\in V(G)$ and $v\in V(H)$. Let $u_0\in V(G)$ with $d_G(u_0) = \Delta(G)$ and $N_G(u_0) = \{u_1, u_2, \cdots, u_{\Delta(G)}\}$. Let $v_0\in V(H)$ with $d_H(v_0) = \Delta(H)$ and $N_H(v_0) = \{v_1, v_2, \cdots, v_{\Delta(H)}\}$. Then $(u_1, v_0), (u_2, v_0), (u_3, v_0), \cdots, (u_{\Delta(G)}, v_0)$ are the common neighbors of $(u_0, v_1)$ and $(u_0, v_2)$. So $rvd(G\times H)\geq \Delta(G)$. Since $(u_0, v_1), (u_0, v_2), \cdots, (u_0, v_{\Delta(H)})$ are the neighbors that $(u_0, v_1)$ and $(u_0, v_2)$ have in common, we have $rvd(G\times H)\geq \Delta(H)$. Since $rvd(P_3\times K_{1, n-1}) = \Delta(K_{1, n-1})$, the lower bound is sharp. Obviously, $rvd(G\times H)\leq |V(H)||V(G)|$. Since $rvd(K_{p}\times K_q) = pq$, where $p\geq 4$ and $q\geq 4$, the upper bound is sharp. □

Corollary 3.6. For nontrivial connected graphs $G$ and $H$, $rvd(G\times H) = 1$ if and only if $G\times H = K_2 \times T$ or $T\times K_2$, where $T$ is a tree.

Proof. Assume that $rvd(G\times H) = 1$. Then $\Delta(G) = 1$ or $\Delta(H) = 1$ by Theorem 3.5. Suppose that $\Delta(G) = 1$ by symmetry. Then $G$ is $K_2$. Let $V(G) = \{x, y\}$. Suppose that $H$ contains a cycle $C_l = v_1v_2\cdots v_lv_1$. If $l$ is even, there exists a cycle $(x, v_1)(y, v_{2})(x, v_{3})(y, v_{4})\cdots (y, v_{l})(x, v_{1})$ in $G\times H$. If $l$ is odd, there exists a cycle $(x, v_{1})(y, v_{2})(x, v_{3})\cdots (x, v_{l})(y, v_{1})(x, v_{2})(y, v_{3})\cdots (y, v_{l})(x, v_{1})$ in $G\times H$. So $rvd(G\times H)\geq 2$. It is a contradiction. Thus, $H$ is a tree.

For the converse, we prove $rvd(K_2\times T) = 1$ by contradiction. Suppose that there is a tree $T_0$ satisfying $rvd(K_2\times T_0)\geq 2$. Then there is a cycle $C$ in $K_2\times T_0$. By symmetry, assume that $C = (x, v_{i_1})(y, v_{i_2})(x, v_{i_3})\cdots (y, v_{i_t})(x, v_{i_1})$. If the cycle $C$ passes $(y, v_{i_k}) = (y, v_{i_1})$, then there exists a cycle $v_{i_1}v_{i_2}\cdots v_{i_{k-1}}v_{i_1}$ in $T_0$; otherwise, there exists a cycle $v_{i_1}v_{i_2}\cdots v_{i_{t}}v_{i_1}$ in $T_0$. It is a contradiction. □

The subsequent corollary is obtained by Corollary 3.6 and Lemma 2.14. For $K_2\times C_n$, where $C_n$ is a cycle with $n$ vertices, the lower bound is sharp. The upper bound is sharp for $K_2\times K_p$, where $p\geq 4$.

Corollary 3.7. For a 2-connected graph $G$: $2\leq rvd(K_2\times G)\leq |V(G)|$.

Any pair of vertices at a distance $\leq 2$ receives different colors in a $2$-distance coloring of a graph $G$. The smallest number of colors required in a $2$-distance coloring of $G$ is $2$-distance chromatic number, represented by $\chi^2(G)$. For any graph $G$, $\Delta+1\leq \chi^2(G)\leq \Delta^2+1$, where $\Delta = \Delta(G)$. As shown in ^[12], the upper bound is sharp for Moore graphs of type $(\Delta, 2)$, which are graphs where all vertices have degree $\Delta$, are at distance at most two from each other, and the total number of vertices is $\Delta^2+1$.

Theorem 3.8. For nontrivial connected graphs $G, H$ with $\Delta(G) = \Delta$, $rvd(G\circ H)\leq \chi^2(G)|V(H)|\leq (\Delta^2+1)|V(H)|$.

Proof. Let $V(G) = \{u_0, u_1, \cdots, u_{p}\}$ and $V(H) = \{v_0, v_1, \cdots, v_q\}$, where $u_0$ is the vertex with the maximum degree of $G$. Let $S_i = \{(u_i, v_j)|j = 0, 1, 2, \cdots, q\}$. Since $(u_{i'}, v_0)$ and $(u_{i'}, v_1)$ are two common neighbors for any pair of vertices in $S_i$, where $u_{i}$ is adjacent to $u_{i'}$ in $G$, $S_i$ is rainbow under any rvd-coloring by Lemma 3.2.

Assume that $N_G(u_0) = \{u_1, u_2, \cdots, u_{\Delta}\}$. For $(u_{i_1}, v_{j_1})\in S_{i_1}$ and $(u_{i_2}, v_{j_2})\in S_{i_2}$, where $i_1, i_2\in [\Delta]$, they have at least two common neighbors $(u_0, v_0)$ and $(u_0, v_1)$. So $\bigcup\limits_{i = 1}^{\Delta}S_{i}$ is rainbow. For $(u_{0}, v_{t})\in S_{0}$ and $(u_{i}, v_{j})\in S_{i}$, where $i\in [\Delta]$, they have at least two common neighbors $(u_0, v_{t'})$ and $(u_{i}, v_{j'})$, where $v_t\sim v_{t'}$ and $v_j\sim v_{j'}$ in $H$. So $\bigcup\limits_{i = 0}^{\Delta}S_{i}$ is rainbow. Thus, $rvd(G)\geq (\Delta+1)|V(H)|$. Similarly, $S_{i}\bigcup(\bigcup\limits_{t = p_1}^{p_d}S_{t})$ is rainbow for any $u_i\in V(G)$, where $N_G(u_i) = \{u_{p_1}, u_{p_2}, \cdots, u_{p_d}\}$.

For a $2$-distance coloring $c'$ of $G$: $V(G)\mapsto [\chi^2(G)]$, we expand each color $k$ to a color set $c_k = \{(k-1)|V(H)|+1, (k-1)|V(H)|+2, \cdots, k|V(H)|\}$. If $c'(u_i) = k$, then color $S_i$ using $c_k$. The resulting coloring of $G\circ H$ is an RVD-Coloring of $G\circ H$. So $\chi^2(G)|V(H)|\geq rvd(G\circ H)$. □

4.   Complexity results

In this section, the complexity of computing rvd number of split graphs is studied. If a split graph $G$ is partitioned into a clique $C$ and an independent set $I$, then define $(C, I)$ as a split partition of $G$. If $|C| = 1$, $G$ is a tree and $rvd(G) = 1$. If $|C| = 2$, $rvd(G) = t+1$, where $t$ is the number of vertices in $I$ that have degree two. So in the rest of this section, we consider $|C|\geq 3$.

Lemma 4.1. ^[1] For an integer $n\geq 2$,

Lemma 4.2. Let $G$ be a graph from $K_n$ ($n\geq 3$) by adding a vertex $v$ with degree $\geq 3$ to $K_n$. Then $rvd(G) = n+1$.

Proof. When $n = 3$, $G$ is $K_4$, and $rvd(G) = 4$ by Lemma 4.1. When $n\geq 4$, assume that $x_1, x_2, x_3\in N_G(v)$. Since there exist $x_1$-$x_2$, $x_1$-$x_3$, $x_2$-$x_3$ rainbow vertex-cuts under any rvd-coloring of $G$, $v$'s color differs from $K_n$. So $rvd(G) = n+1$. □

Theorem 4.3. For a split graph $G$, there exists a polynomial time algorithm that approximates $rvd(G)$ within a factor of $n^{\frac{2}{3}}$.

Proof. Let $G$ be a connected graph with a clique $X$ and an independent set $Y$. Consider that $G$ is 2-connected by Lemma 2.13. So $\delta(G)\geq 2$. Let $p = |X|-1$ for $|X| = 3$ and $p = |X|$ for $|X|\geq 4$. Construct a new graph $H$ using $Y$. If $u, v\in Y$ and $u, v$ have at least two common neighbors in $X$, then $u\sim v$; otherwise, $u\not\sim v$.

Now we claim $p+\chi(H)-1\leq rvd(G)\leq |X|+\chi(H)$. First, provide a vertex-coloring $c$ on $G$. Color $X$ rainbow using $|X|$ colors. Color $Y$ using new $\chi(H)$ colors according to the proper coloring of $H$. Let $w, z\in V(G)$. If $w, z\in X$, then $\mathcal{F}_G(w, z) = X\cup M_{Y}(w, z)\setminus\{w, z\}$, where $M_{Y}(w, z) = N_Y(w)\cap N_Y(z)$. If $w\in Y$ or $z\in Y$, $\mathcal{F}_G(w, z) = X\setminus\{w, z\}$. So $rvd(G)\leq |X|+\chi(H)$. We prove the lower bound by contradiction. Assume that $rvd(G)\leq p+\chi(H)-2$. Denote an RVD-Coloring of $G$ by $c_0$ using $p+\chi(H)-2$ colors. Since $X$ is a complete graph, $rvd(X) = p$. Then $Y$ has at most $\chi(H)-2$ colors different from $X$, denoted by $[\chi(H)-2]$. Let $S = \{v|v\in Y\ \text{and}\ c_0(v)\in c_0(X)\}$. For $v\in S$, by Lemma 4.2, we have $d_G(v) = 2$. Now recolor $S$ to get a vertex-coloring $c'$ on $G$. Assume that $N_G(v) = \{u_1, u_2\}$. If $M_{Y}(u_1, u_2) = \{v\}$, recolor $v$ such that $c'(v)\in [\chi(H)-2]$; otherwise, recolor $v$ using a new color. So $Y$ uses at most $\chi(H)-1$ colors in $c'$ and has no color appearing in $X$. Color $H$ as $Y$. Then we obtain a proper coloring of $H$ using at most $\chi(H)-1$ colors, which is a contradiction. So $rvd(G)\geq p+\chi(H)-1$.

Consider color classes $V_1, V_2, \cdots, V_{\chi(H)}$ of $H$. Since $\delta(G)\geq 2$ and any two vertices in $V_i$ ($i\in [\chi(H)]$) have at most one common neighbor in $X$, we have $\binom{|X|}{2}\geq |V_i|$ for any $i\in [\chi(H)]$. Thus, $\binom{|X|}{2}\geq \frac{|V(H)|}{\chi(H)}$. We obtain $\chi(H)\geq \frac{2|V(H)|}{|X|^2}$. Any graph with $t$ edges can be colored properly with at most $\frac{1}{2}+\sqrt{2t+\frac{1}{4}}$ colors in chapter 5 ^[8]. We can obtain an RVD-Coloring $c_0$ of $G$ using at most $|X|+1+\sqrt{2|E(H)|}$ colors. So we obtain the following inequalities for $n\geq 22$:

Hence, $c_0$ is an $n^{\frac{2}{3}}$-approximation of $rvd(G)$. □

Next, we consider RVD-Problem, which aims to determine whether $G$ has an RVD-Coloring with $k$ colors given the graph $G$ and a positive integer $k$.

We have proved Lemma 4.4 in ^[14]. The main idea of Lemma 4.4 is to construct a split graph $H$ from any graph $G$ satisfying $rvd(H)\leq k+3|E(G)|$ if and only if $\chi(G)\leq k$. A graph is induced $K_{1, t}$-free if it does not contain $K_{1, t}$ as an induced subgraph. In fact, $H$ is an induced $K_{1, t}$-free split graph for $t\geq 4$. So we easily obtain Theorem 4.5.

Lemma 4.4. ^[14] RVD-Problem is NP-complete for split graphs.

Theorem 4.5. RVD-Problem is NP-complete for induced $K_{1, t}$-free split graphs for $t\geq 4$.

Furthermore, we consider induced $K_{1, t}$-free split graphs with $t\leq 3$.

Lemma 4.6. If $G$ is an induced $K_{1, 2}$-free connected graph, then $G$ is a complete graph.

Proof. Assume that $G$ is not complete. Then there exist two vertices, $u$ and $v$, such that $uv\not\in E(G)$. Since $G$ is connected, there is a path from $u$ to $v$, denoted by $P_{uv} = uw_1w_2\cdots w_kv$. Since $G$ is induced $K_{1, 2}$-free, we have $uw_2\in E(G)$ and get a shorter path $uw_2\cdots w_kv$. Similarly, we have $uw_3, uw_4\cdots uw_k, uv\in E(G)$, which is a contradiction. □

According to Lemmas 4.1 and 4.6, we get the following result.

Theorem 4.7. For an induced $K_{1, 2}$-free split graph $G$ with order $n$,

.

Theorem 4.8. For an induced $K_{1, 3}$-free split graph $G$, $rvd(G)$ can be determined in polynomial time.

Proof. Let $G$ be an induced $K_{1, 3}$-free split graph with split partition $(C, I)$. Since $G$ is induced $K_{1, 3}$-free, each vertex in $C$ has at most two neighbors in $I$ ($\bf{Rule 1}$). For $u, v\in I$, if $N_G(u)\cap N_G(v)\neq \emptyset$, then $N_G(u)\cup N_G(v) = C$ ($\bf{Rule 2}$). Otherwise, there exists a vertex $v_0\in C$ satisfying $v_0\not\sim u$ and $v_0\not\sim v$. Let $v'\in N_G(u)\cap N_G(v)$. The vertices $v', u, v, v_0$ form a $K_{1, 3}$, which is a contradiction.

For $|C| = 3$, if there is no vertex in $I$ with degree$\geq 2$, then $rvd(G) = 2$; if there is a vertex with degree two but no vertex with degree three in $I$, then $rvd(G) = 3$; if there is a vertex with degree three in $I$, then $C$ is rainbow under any rvd-coloring of $G$. So we only need to consider the last case for $|C| = 3$ and $|C|\geq 4$.

Let $S = \{(u, v)||N_G(u)\cap N_G(v)|\geq 2 \text{ and } d_G(u)\geq 3, d_G(v)\geq 3, \text{ and } u, v\in I\}$. If $(u, v)\in S$ and $(x, y)\in S$, let $v_s\in N_G(u)\cap N_G(v)$; then $v_s\sim x$ or $v_s\sim y$ by Rule 2. We obtain $d_I(v_s)\geq 3$, which is a contradiction to Rule 1. So $S$ has no two disjoint pairs of vertices. Here are two cases.

Case 1. Assume that $(u, v), (u, x), (v, x)\in S$.

By Rule 2, each vertex in $C$ has two edges to $\{u, v, x\}$. So by Rule 1, $|I| = 3$ and $I = \{u, v, x\}$. Thus, $S = \{(u, v), (u, x), (v, x)\}$.

Case 2. $|S| = 1$ or every pair of vertices in $S$ contains the same vertex.

Assume that the same vertex is $u$. Then let $S = \{(u, u_1), (u, u_2)\cdots\}$.

Next, we give a vertex-coloring $c$ of the induced $K_{1, 3}$-free split graph $G$ with split partition $(C, I)$ as follows.

We now assert that $c$ is $G$'s rvd-coloring. By Lemmas 4.2 and 3.2, the number of colors used in vertex-coloring $c$ is the lower bound of $rvd(G)$. Let $q, q'\in V(G)$. For $q, q'\in C$, since $G$ is induced $K_{1, 3}$-free, there is at most one common neighbor with degree two in $I$. Let $N_I(q, q')$ be the common neighbors of $q$ and $q'$ in $I$. Then $\mathcal{F}_G(q, q') = C\cup N_I(q, q')\setminus\{q, q'\}$. For $q, q'\in I$, $\mathcal{F}_G(q, q') = C$. For $q\in C$ and $q'\in I$, $\mathcal{F}_G(q, q') = C\setminus\{q\}$. □

Use of Generative-AI tools declaration

The author declares she has not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgments

The author is very grateful to the anonymous reviewers for their constructive feedback, which helped strengthen this work. This work is supported by the Scientific Research Funds of Zhejiang Sci-Tech University, PR China (Project No. 21062343-Y).

Conflict of interest

No conflict of interest exists in the submission of this manuscript.