Complexity results for two kinds of colored disconnections of graphs

Abstract

The concept of rainbow disconnection number of graphs was introduced by Chartrand et al. in 2018. Inspired by this concept, we put forward the concepts of rainbow vertex-disconnection and proper disconnection in graphs. In this paper, we first show that it is $NP$-complete to decide whether a given edge-colored graph $G$ with maximum degree $\Delta (G)=4$ is proper disconnected. Then, for a graph $G$ with $\Delta (G)\le 3$ we show that $pd(G)\le 2$ and determine the graphs with $pd(G)=1$ and $2$, respectively. Furthermore, we show that for a general graph $G$, deciding whether $pd(G)=1$ is $NP$-complete, even if $G$ is bipartite. We also show that it is $NP$-complete to decide whether a given vertex-colored graph $G$ is rainbow vertex-disconnected, even though the graph $G$ has $\Delta (G)=3$ or is bipartite.

15 pages, 8 figures