---
abstract: |
    For an edge-colored graph $G$, a set $F$ of edges of $G$ is called a *proper edge-cut* if $F$ is an edge-cut of $G$ and any pair of adjacent edges in $F$ are assigned by different colors.  An edge-colored graph is called *proper disconnected* if for each pair of distinct vertices of $G$ there exists a proper edge-cut separating them.  For a connected graph $G$, the *proper disconnection number* of $G$, denoted by $pd(G)$, is defined as the minimum number of colors that are needed to make $G$ proper disconnected.  In this paper, we first show that it is $NP$-complete to decide whether a given $k$-edge-colored graph $G$ with $\Delta(G)=4$ is proper disconnected.  Then, for a graph $G$ with $\Delta(G)\leq 3$ we show that $pd(G)\leq 2$ and determine the graphs with $pd(G)=1$ and $2$, respectively.  Finally, we show that for a general graph $G$, deciding whether $pd(G)=1$ is $NP$-complete, even if $G$ is bipartite.\
    **Keywords:** edge-coloring; proper edge-cut; proper disconnection number; complexity; $NP$-complete.\
    **AMS subject classification 2010:** 05C15, 05C40, 05C85, 68Q17, 68Q25, 68R10.\
author:
- |
    [You Chen, Ping Li, Xueliang Li, Yindi Weng]{}\
    [Center for Combinatorics and LPMC]{}\
    [Nankai University, Tianjin 300071, China]{}\
    [chen\_you@163.com, wjlpqdxs@163.com]{}\
    [lxl@nankai.edu.cn, 1033174075@qq.com]{}\
title: ' **Complexity results for the proper disconnection of graphs[^1]**'
---

Introduction
============

All graphs considered in this paper are finite, simple and undirected.  Let $G=(V(G),E(G))$ be a nontrivial connected graph with vertex set $V(G)$ and edge set $E(G)$. For $v\in V(G)$, let $d(v)$ denote the $degree$ of $v$ in $G$. We denote by $N(v)$ the $neighborhood$ of $v$ in $G$ and by $N[v]$ the closed neighborhood of $v$ in $G$. For any notation and terminology not defined here, we follow those used in [@BM]. 

For a graph $G$ and a positive integer $k$, let $c: E(G)\rightarrow[k]$ be an edge-coloring of $G$, where and in what follows $[k]$ denotes the set $\{1,2,...,k\}$ of integers.  For an edge $e$ of $G$, we denote the color of $e$ by $c(e)$. If adjacent edges of $G$ receive different colors under $c$, the edge-coloring $c$ is called *proper*.  The *chromatic index* of $G$, denoted by $\chi'(G)$, is the minimum number of colors needed in a proper edge-coloring of $G$.

Chartrand et al.  in [@CDHHZ] introduced the concept of rainbow disconnection of graphs.  An *edge-cut* of a graph $G$ is a set $R$ of edges such that $G-R$ is disconnected.  An edge-coloring is called a *rainbow disconnection coloring* of $G$ if for every two vertices of $G$, there exists a rainbow edge-cut in $G$ separating them.  For a connected graph $G$, the *rainbow disconnection number* of $G$, denoted $rd(G)$, is the smallest number of colors required for a rainbow disconnection coloring of $G$. A rainbow disconnection coloring using $rd(G)$ colors is called an rd-*coloring* of $G$. In [@BCL] the authors obtained many results on the rainbow disconnection number. 

As an opposite counterpart concept of rainbow disconnection of graphs, we put forward the concept of monochromatic disconnection of graphs.  For details we refer to [@PL1; @PL2]. 

In [@BCJ], the authors introduced the concept of proper disconnection of graphs.  For an edge-colored graph $G$, a set $F$ of edges of $G$ is a *proper edge-cut* if $F$ is an edge-cut of $G$ and any pair of adjacent edges in $F$ are assigned by different colors.  For any two vertices $x,y$ of $G$, an edge set $F$ is called an $x$-$y$ proper edge-cut if $F$ is a proper edge-cut and $F$ separates $x$ and $y$ in $G$. An edge-colored graph is called *proper disconnected* if for each pair of distinct vertices of $G$ there exists a proper edge-cut separating them.  For a connected graph $G$, the *proper disconnection number* of $G$, denoted by $\mathit{pd(G)}$, is defined as the minimum number of colors that are needed to make $G$ proper disconnected, and such an edge-coloring is called a pd-*coloring*.  From [@BCJ], we know that if $G$ is a nontrivial connected graph, then $1\leq \mathit{pd}(G)\leq \mathit{rd}(G)\leq \chi'(G)\leq \Delta(G)+1$.

This paper is organized as follows.  In Section 2, we first show that it is $NP$-complete to decide whether a given $k$-edge-colored graph $G$ with $\Delta(G)=4$ is proper disconnected.  Then, for a graph $G$ with $\Delta(G)\leq 3$ we show that $pd(G)\leq 2$, and determine the graphs with $pd(G)=1$ and $2$, respectively.  We further show that if $G$ is a graph with $\Delta(G)=3$ and the set of vertices with degree $3$ in $G$ is an independent set, then deciding whether $pd(G)=1$ is solvable in polynomial time.  Then we propose a question for further study: Is it true that deciding whether $pd(G)=1$ is solvable in polynomial time for a graph $G$ with $\Delta(G)=3$ ?  In Section 3, we show that for a general graph $G$, deciding whether $pd(G)=1$ is $NP$-complete, even if the graph is bipartite. 

Hardness results for graphs with maximum degree four
====================================================

In this section, we show that it is $NP$-complete to decide whether a given $k$-edge-colored graph $G$ with $\Delta(G)=4$ is proper disconnected.  Then we give the proper disconnection numbers of graphs with $\Delta(G)\leq 3$, and propose a question. 

We first give some notations.  For an edged-colored graph $G$, let $F$ be a proper edge-cut of $G$. If $F$ is a matching, then $F$ is called a *matching cut*.  Furthermore, if $F$ is an $x$-$y$ proper edge-cut for vertices $x,y\in G$, then $F$ is called an $x$-$y$ *matching cut*.  For a vertex $v$ of $G$, let $E_v$ denote the edge set consisting of all edges incident with $v$ in $G$.

We can obtain the following results by means of a reduction from the NAE-3-SAT problem.  We now present the NAE-3-SAT problem, which is $NP$-complete; see [@sch78; @DD19]. 

[**Problem:** ]{} Not-All-Equal 3-Sat (NAE-3-SAT)

[**Instance:** ]{}A set $C$ of clauses, each containing 3 literals from a set of boolean variables. 

[**Question:**]{} Can truth value be assigned to the variables so that each clause contains at least one true literal and at least one false literal ? 

Given a formula $\phi$ with variable $x_1,\cdots,x_n$, let $\phi=c_1\wedge c_2\wedge\cdots\wedge c_m$, where $c_i=(l_1^i\vee l_2^i\vee l_3^i)$. Then $l_j^i\in\{x_1,\overline{x_1},\cdots,x_n,\overline{x_n}\}$ for each $i\in[m]$ and $j\in[3]$.

![ The graphs $I_j$ and $C_i$.[]{data-label="SAT1"}](pdhard1.eps "fig:"){width="234pt"}\

We will construct a graph $G_\phi$ below.  The graphs $I_j$ and $C_i$ are shown in Figure \[SAT1\] where $j\in[n]$ and $i\in[m]$. Each graph $C_i$ has two pairs of parallel edges.  The graph $G_\phi$ (see Figure \[SAT11\]) is obtained from mutually disjoint graphs $I_j$ and $C_i$ by adding a pair of parallel edges between $z$ and $w$ if $z,w$ satisfy one of the following conditions:

1.   $z=a_i$ and $w=a_{i+1}$ for some $i\in[n+2m-1]$;

2.   $z=b_i$ and $w=b_{i+1}$ for some $i\in[n+2m-1]$;

3.   $z=x_j$, $w=l_t^i$ and $x_j=l_t^i$ for some $j\in[n], t\in[3]$ and $i\in[m]$;

4.   $z=\overline{x_j}$, $w=l_t^i$ and $\overline{x_j}=l_t^i$ for some $j\in[n], t\in[3]$ and $i\in[m]$.

![ The graph $G_\phi$ with $l_3^1=l_1^2=\overline{x_1}$.[]{data-label="SAT11"}](pdhard11.eps "fig:"){width="320pt"}\

In fact, the graph $G_\phi$ was constructed in [@PP] (in Section 3.2).  It is obvious that each vertex of $G_\phi$ with degree greater than four is a vertex with even degree.  Moreover, there are two simple edges incident with this kind of vertex, and the other edges incident with the vertex are some pairs of parallel edges.  The authors proved that $G_\phi$ has a matching cut if and only if the corresponding instance $\phi$ of NAE-3-SAT problem has a solution. 

We present a [*star structure*]{} as shown in Figure \[Star\] (1).  Each vertex $z_i$ is called a [*tentacle*]{}.  A star structure is a [*$k$-star structure*]{} if it has $k$ tentacles. 

![( 1) A $6$-star structure with tentacles $z_1,\cdots,z_6$, and (2) the operation $\mathcal{O}$ on vertex $y$ with degree $16$.[]{data-label="Star"}](Star.eps "fig:"){width="350pt"}\

For a vertex $y$ of $G_\phi$ with $d_{G_\phi}(y)=2t+2>4$, assume $N(y)=\{w_1,\cdots,w_{t+2}\}$ such that $w_{t+1},w_{t+2}$ connect $y$ by a simple edge respectively, and $w_i$ connects $y$ by a pair of parallel edges for $i\in[t]$. Now we define an operation $\mathcal{O}$ on vertex $y$: replace $y$ by a $(t+1)$-star structure with tentacles $z_1,\cdots,z_{t+1}$ such that $w_{i}$ and $z_{t+1}$ for $i\in \{t+1,t+2\}$ are connected by a simple edge, and $z_i$ and $w_i$ are connected by parallel edges for $i\in[t]$. As an example, Figure \[Star\] (2) shows the operation $\mathcal{O}$ on vertex $y$ with degree $16$. We apply the operation $\mathcal{O}$ on each vertex of degree greater than four, and then subdivide one of each pair of parallel edges using a new vertex in $G_\phi$. Denote the resulting graph by $G'_\phi$, which is a simple graph.  The graph $G'_\phi$ was also defined in [@PP], and the authors proved that $G'_\phi$ has a matching cut if and only if the corresponding instance $\phi$ of NAE-3-SAT problem has a solution. 

Now we construct a graph, denoted by $H_\phi$, obtained from $G_\phi$ by operations as follows.  Add two new vertices $u$ and $v$. Connect $u$ and each vertex of $\{a_1,a_{n+2m}\}$ by a pair of parallel edges, and connect $v$ and each vertex of $\{b_1,b_{n+2m}\}$ by a pair of parallel edges.  We apply the operation $\mathcal{O}$ on each vertex of degree greater than four in $H_\phi$, and then subdivide one of each pair of parallel edges using a new vertex.  Denote the resulting graph by $H'_\phi$ (see Figure \[SAT22\]), which is a simple graph.  Observe that $\Delta(H'_\phi)=4$. Since a minimal matching cut cannot contain any edge in a triangle, we have that there is a $u$-$v$ matching cut in $H'_\phi$ if and only if there is a matching cut in $G'_\phi$. Thus, there is a $u$-$v$ matching cut in $H'_\phi$ if and only if the instance $\phi$ of NAE-3-SAT problem has a solution. 

![ The graph $H'_\phi$ with $l_3^1=l_1^2=\overline{x_1}$.[]{data-label="SAT22"}](pdhard22.eps "fig:"){width="300pt"}\

\[NPC\] For a fixed positive integer $k$, let $G$ be a $k$-edge-colored graph with $\Delta(G)=4$, and let $u,v$ be any two specified vertices of $G$. Then deciding whether there is a $u$-$v$ proper edge-cut in $G$ is $NP$-complete. 

For a connected graph $G$ with an edge-coloring $c: E(G)\rightarrow [k]$ and an edge-cut $D$ of $G$, let $M_i=\{e\ |\  e\in D \mbox{ and } c(e)=i\}$ for $i\in [k]$. Then $D$ is a proper edge-cut if and only if each $M_i$ is a matching.  Therefore, deciding whether a given edge-cut of an edge-colored graph is a proper edge-cut is in $P$.

For an instance $\phi$ of the NAE-3-SAT problem, we can obtain the corresponding graph $H'_\phi$ as defined above.  Then there is a vertex, say $y'$, of $H'_\phi$ with degree two.  Let $G$ be a graph obtained from $H'_\phi$ and a path $P$ of order $k$ by identifying $y'$ and one end of $P$. Then $\Delta(G)=4$. We color each edge of $G-E(P)$ by $1$ and color $k-1$ edges of $P$ by $2,3,\cdots,k$, respectively.  Then the edge-coloring is a $k$-edge-coloring of $G$, and there is a $u$-$v$ proper edge-cut in $G$ if and only if there is a $u$-$v$ matching cut in $H'_\phi$. Thus, we have that there is a $u$-$v$ proper edge-cut in $G$ if and only if the instance $\phi$ of NAE-3-SAT problem has a solution. 

\[cor\] For a fixed positive integer $k$, let $G$ be a $k$-edge-colored graph with $\Delta(G)=4$. Then it is $NP$-complete to decide whether $G$ is proper disconnected. 

Even though it is still not clear for the computational complexity of deciding whether a graph with maximum degree at most three is proper disconnected, we will show that $pd(G)\leq 2$ for a graph $G$ with $\Delta(G)\leq 3$ and then determine the graphs with $pd(G)=1$ and $2$, respectively.  Some useful results are given as follows, which will be used in the sequel. 

[@BCJ]\[treepd\] If $G$ is a tree, then $pd(G)=1$.

[@BCJ]\[cyclepd\] If $C_n$ be a cycle, then $$\textnormal{pd}(C_n)=\left\{
\begin{array}{lcl}
2, &  {if~n=3},\\
1, &  {if~n\geq 4.} 
\end{array}
\right.$$

[@BCJ]\[t2\] For any integer $n\geq 2$, $pd(K_{n})=\lceil \frac{n}{2} \rceil$.

[@BCJ]\[pd1\] Let $G$ be a nontrivial connected graph.  Then $pd(G)=1$ if and only if for any two vertices of $G$, there is a matching cut separating them. 

[@BM]\[perfectmatching\] (Petersen’s Theorem) Every $3$-regular graph without cut edges has a perfect matching. 

For a simple connected graph $G$, if $\Delta(G)=1$, then $G$ is the graph $K_2$, a single edge.  If $\Delta(G)=2$, then $G$ is a path of order $n\geq 3$ or a cycle.  By Theorems \[treepd\] and \[cyclepd\], for a connected graph $G$ with $\Delta(G)\leq 2$, we have $pd(G)=1$ if and only if $G$ is a path or a cycle of order $n\geq 4$, and $pd(G)=2$ if and only if $G$ is a triangle. 

Next, we will present the proper disconnection numbers of graphs with maximum degree $3$. At first, we give the proper disconnection numbers of $3$-regular graphs. 

\[lpdnc\] If $G$ is a $3$-regular connected graph without cut edges, then $pd(G)\leq 2$.

![ The graph $G_0$[]{data-label="figpd3regno"}](pd3regno.eps){width="30.00000%"}

Let $G_0$ be a graph by connecting two triangles with $3$ matching edges, and we color $G_0$ with two colors as shown in Figure \[figpd3regno\].  Obviously, it is a proper disconnection coloring of $G_0$. Now we consider $2$-edge-connected $3$-regular graphs $G$ except $G_0$. By Theorem \[perfectmatching\], there exists a perfect matching $M$ in $G$. We define an edge-coloring $c$ of $G$ as follows.  Let $c(M)=2$. If $E(G)\setminus M$ contains triangles, then we color one edge of each triangle by color $2$. We color the remaining edges by color $1$. Since $G\setminus M$ is the union of some disjoint cycles, we denote these disjoint cycles by $C_1,C_2,\cdots C_t$. Let $x,y$ be two vertices of $G$. If $x$ and $y$ belong to different cycles of $C_1,C_2,\cdots C_t$, then $M$ is an $x$-$y$ proper edge-cut.  If $x$ and $y$ belong to the same cycle $C_i$($i\in [t]$), then there are two cases to discuss. 

**Case 1.**  $|C_i|\geq 4$.

Since $|C_i|\geq 4$, there exist two $x$-$y$ paths $P_1,P_2$ in $C_i$. We choose two nonadjacent edges $e_1, e_2$ respectively from $P_1, P_2$. Then $M\cup \{e_1,e_2\}$ is an edge-cut between $x$ and $y$. Since $c(M)=2$ and $c(e_1)=c(e_2)=1$, $M\cup \{e_1,e_2\}$ is an $x$-$y$ proper edge-cut. 

**Case 2.**  $|C_i|=3$.

Since $x,y\in C_i$, we can assume $C_i=xyz$. Let $N(x)=\{y,z,x_0\}$ and $N(x_0)=\{x,x_1,x_2\}$. Assume $x_0\in C_k,k\in [t]\setminus\{i\}$.

[*Subcase 2.1.*]{}  $c(xy)=1$.

Assume $c(yz)=1$ and $c(xz)=2$. We note that $x_1\notin N(z)$ or $x_2\notin N(z)$. Without loss of generality, $x_2\notin N(z)$.

For $|C_k|\geq 4$, we have $c(x_0x_2)=1$. Then $E_{x_2}\setminus \{x_0x_2\}$ have different colors.  So, $\{xy,xz,x_0x_1\}\cup E_{x_2}\setminus \{x_0x_2\}$ is an $x$-$y$ proper edge-cut. 

For $|C_k|=3$, if $c(x_0x_1)\neq c(x_0x_2)$, we get that $\{xy,xz,x_0x_1,x_0x_2\}$ is an $x$-$y$ proper edge-cut.  Now consider $c(x_0x_1)=c(x_0x_2)=1$. If $x_1\in N(z)$, then $c(x_1z)=2$. Since $G\neq G_0$, we have $x_2\notin N(y)\cup N(z)$. So $(E_y\setminus \{yz\})\cup\{xz,x_0x_1,x_1x_2\}$ is an $x$-$y$ proper edge-cut.  If $x_1\notin N(z)$, then we denote $E_{x_1}\setminus \{x_0x_1,x_1x_2\}$ by $e_1$ and denote $E_{x_2}\setminus \{x_0x_2,x_1x_2\}$ by $e_2$. It is clear that $e_1,e_2\in M$. So, $c(e_1)=c(e_2)=2$. We get that $\{xy,xz,e_1,e_2\}$ is an $x$-$y$ proper edge-cut. 

[*Subcase 2.2.*]{}  $c(xy)=2$.

In Subcase $2.1$, if $c(xy)=1$, then the $x$-$y$ proper edge-cut is also an $x$-$z$ proper edge-cut.  So, we have proved Subcase $2.2$.

Let $H(v)$ be a connected graph with one vertex $v$ of degree two and the remaining vertices of degree three.  We assume that the neighbors of $v$ in $H(v)$ are $v_1$ and $v_2$, respectively.  If $v_1$, $v_2$ are adjacent, then we denote it by $H_1(v)$. Otherwise, we denote it by $H_2(v)$. Let $H_1'(v)$ be the graph obtained by replacing the vertex $v$ by a diamond.  Let $H_2'(v)$ be the graph by replacing the path $v_1vv_2$ of $H_2(v)$ by an new edge $v_1v_2$. See Figure \[gpro\]. 

![ The graph process[]{data-label="gpro"}](pd1.eps){width="70.00000%"}

\[pd3regular\] If $G$ is a $3$-regular graph of order $n$ $(n\geq 4)$, then $pd(G)\leq 2$.

$Proof.$ We proceed by induction on the order $n$ of $G$. A $3$-regular graph of order $4$ is $K_4$ and $pd(K_4)=2$ from Theorem \[t2\].  So, the result is true for $n=4$. Suppose that if $H$ is a $3$-regular graph of order $n$ $(n\geq 4)$, then $pd(G)\leq 2$. Let $G$ be a $3$-regular graph of order $n+1$. We will show $pd(G)\leq 2$. If $G$ has no cut edge, then $pd(G)\leq 2$ from Lemma \[lpdnc\].  So, we consider $G$ having a cut edge, say $uv$ $(u,v\in V(G))$. We delete the cut edge $uv$, then there are two components containing $u$ and $v$, respectively, say $G_1$, $G_2$. Since $G$ is $3$-regular, we have $|V(G_1)|\geq 5$ and $|V(G_2)|\geq 5$. Thus, $5\leq|V(G_1)|\leq n-4$ and $5\leq|V(G_2)|\leq n-4$. Obviously, $G_1$ and $G_2$ are the graphs $H(u)$, $H(v)$, respectively.  We first show the following claims. 

\[lpd2\] $pd(H_1(u))\leq 2$.

$Proof.$ Let $u_1$ and $u_2$ be two neighbors of $u$ in $H_1(u)$. Assume that the neighbors of $u_1$ and $u_2$ in $H_1(u)$ are $\{u, u_2, w_1\}$, $\{u, u_1, w_2\}$, respectively.  The edges $u_1w_1$, $u_1u_2$ and $u_2w_2$ are denoted by $e_1,e_2,e_3$. Let $A=\{u,u_1,u_2\}$ and $B=V(H_1(u))\setminus A$.  Since $|V(G_1)|\leq n-4$, we have $|V(H_1'(u))|\leq n-1$. Obviously, $H_1'(u)$ is $3$-regular.  Then $pd(H_1'(u))\leq 2$ by the induction.  Let $c'$ be a proper disconnection coloring of $H_1'(u)$ with two colors.  For any two vertices $p$ and $q$ of $H_1'(u)$, let $R_{pq}$ be a $p$-$q$ proper edge-cut of $H_1'(u)$. There are two cases to discuss. 

**Case 1**.  $c'(e_1)=c'(e_2)$ or $c'(e_2)=c'(e_3)$.

Without loss of generality, we assume $c'(e_1)=c'(e_2)=1$. We define an edge-coloring $c$ of $H_1(u)$ as follows.  Let $c(uu_1)=2$, $c(uu_2)=1$ and $c(e)=c'(e)$ $(e\in E(H_1(u))\setminus\{uu_1,uu_2\})$. Let $x$ and $y$ be two vertices of $H_1(u)$. If they are both in $H_1(u)\setminus\{u\}$, then $(R_{xy}\cap E(H_1(u)))\cup\{uu_1\}$ is an $x$-$y$ proper edge-cut of $H_1(u)$. If $x=u$ or $y=u$, then $E_u$ is an $x$-$y$ proper edge-cut of $H_1(u)$. So, $c$ is a proper disconnection coloring of $H_1(u)$. Thus, $pd(H_1(u))\leq 2$.

**Case 2**.  $c'(e_1)=c'(e_3)\neq c'(e_2)$.

Assume $c'(e_1)=c'(e_3)=1$ and $c'(e_2)=2$. Define an edge-coloring $c$ of $H_1(u)$ as follows.  Let $c(uu_1)=2$, $c(uu_2)=1$ and $c(e)=c'(e)$ $(e\in E(H_1(u))\setminus\{uu_1,uu_2\})$. Let $x$ and $y$ be two vertices of $H_1(u)$. If $x=u$ or $y=u$, then $E_u$ is an $x$-$y$ proper edge-cut of $H_1(u)$. If $x,y\in A\setminus\{u\}$, then $\{uu_2,e_1,e_2\}$ is an $x$-$y$ proper edge-cut of $H_1(u)$. If $x\in A\setminus\{u\},y\in B$ or $x\in B, y\in A\setminus\{u\}$, then $\{e_1,e_3\}$ is an $x$-$y$ proper edge-cut of $H_1(u)$. Considering $x,y\in B$, if $e_1,e_3\notin R_{xy}$, then $(R_{xy}\cap E(H_1(u)))\cup\{uu_2\}$ is an $x$-$y$ proper edge-cut of $H_1(u)$. Otherwise, i.e., $e_1\in R_{xy}$ or $e_3\in R_{xy}$, then $R_{xy}\cap E(H_1(u))$ is an $x$-$y$ proper edge-cut of $H_1(u)$. So, $c$ is a proper disconnection coloring of $H_1(u)$. Thus, $pd(H_1(u))\leq 2$.

\[lpd2\] $pd(H_2(u))\leq 2$.

Assume that the neighbors of $u$ in $H_2(u)$ are $u_1$ and $u_2$. Since $|V(H_2'(u))|<|V(G_2)|$ and $H_2'(u)$ is $3$-regular.  Then $pd(H_2'(u))\leq 2$ by the induction.  Let $c'$ be a proper disconnection coloring of $H_2'(u)$ with two colors.  We define an edge-coloring $c$ of $H_2(u)$ as follows: $c(uu_1)=1, c(uu_2)=2$ and $c(e)=c'(e)$ $(e\in E(H_2(u))\setminus\{uu_1,uu_2\})$. Assume $c'(u_1u_2)=c(uu_i)$ ($i=1$ or $2$).  Then for any two vertices $x$ and $y$ of $H_2(u)$, if $x=u$ or $y=u$, then $E_u$ forms an $x$-$y$ proper edge-cut.  Otherwise, assume the $x$-$y$ proper edge-cut in $H_2'(u)$ is $R$. If $u_1u_2\notin R$, then $R$ is an $x$-$y$ proper edge-cut.  If $u_1u_2\in R$, then $(R\cup\{uu_i\})\setminus\{u_1u_2\}$ is an $x$-$y$ proper edge-cut.  So, $c$ is a proper disconnection coloring of $H_2(u)$. Thus, $pd(H_2(u))\leq 2$.

So, from above claims we have $pd(G_1)\leq 2$. Similarly, we have $pd(G_2)\leq 2$. Then, there exists a proper disconnection coloring $c_0$ of $G_1\cup G_2$ with two colors.  Now we assign the color $1$ to the cut edge $uv$. It is a proper disconnection coloring of $G$. So, $pd(G)\leq 2$.

A *block* of a graph $G$ is a maximal connected subgraph of $G$ that has no cut vertex.  Let $\{B_1,B_2, ...,B_t\}$ be the set of blocks of $G$.

[@BCJ]\[pdblock\] Let $G$ be a nontrivial connected graph.  Then $\mathit{pd}(G)=\max\{ \mathit{pd}(B_i)\ | \ i=1,2,\ldots, t \}$.

\[pd26\] If $G$ is a graph of order $n$ with $\Delta(G)=3$, then $pd(G)\leq 2$. Particularly, if $G$ satisfies the condition of Theorem \[pd1\], then $pd(G)=1$; otherwise, $pd(G)=2$.

![ The graph H.[]{data-label="1"}](pdmax.eps "fig:"){width="100pt"}\

If $G$ is a tree, then $pd(G)=1$ by Theorem \[treepd\].  Suppose $G$ is not a tree.  Let $H$ be a graph as shown in Figure \[1\].  Call $v$ the [*key vertex*]{} of $H$. Suppose $G$ is a graph with maximum degree three.  Let $G'$ be a graph obtained from $G$ by deleting pendent edges one by one.  Then $\Delta(G')\leq3$ and $pd(G)=pd(G')$ by Lemma \[pdblock\].  Let $\{u_1,\cdots,u_t\}$ be the set of $2$-degree vertices in $G'$ and $H_1,\cdots,H_t$ be $t$ copies of $H$ such that the key vertex of $H_i$ is $v_i$ ($i\in [t]$).  We construct a new graph $G''$ obtained by connecting $v_i$ and $u_i$ for each $i\in[t]$. Then $G''$ is a $3$-regular graph.  By Lemma \[pd3regular\], $pd(G'')\leq2$. Since $G'$ is a subgraph of $G''$, then $pd(G')\leq2$.

Let $G$ be a connected graph with $\Delta=3$ such that the set of vertices with degree $3$ in $G$ forms an independent set.  If $G$ contains a triangle or $K_{2,3}$, then $pd(G)=2$; otherwise, $pd(G)=1$.

If $G$ contains a triangle or a $K_{2,3}$, then there exist two vertices such that no matching cut separates them.  So, $pd(G)=2$ by Theorem \[pd26\].  Now consider that $G$ is triangle-free and $K_{2,3}$-free.  We proceed by induction on the order $n$ of $G$. Since $\Delta(G)=3$, we have $n\geq 4$. If $n=4$, then the graph $G$ is $K_{1,3}$ and $pd(G)=1$ by Theorem \[treepd\].  The result holds for $n=4$. Assume $pd(G)=1$ for triangle-free and $K_{2,3}$-free graphs with order $n$ satisfying the condition.  Now, consider a graph $G$ with order $n+1$. Let $x$ and $y$ be two vertices of $G$.

For $d(x)=1$, the edge $E_x$ is an $x$-$y$ matching cut. 

For $d(x)=d(y)=2$, if $x$ and $y$ are adjacent, let $x_1,y_1$ be another neighbor of $x$ and $y$, respectively.  Let $G'=G-xy$. Then by the induction, there exist an $x_1$-$y_1$ matching cut $R$ in $G'$. Thus, $R\cup\{xy\}$ is an $x$-$y$ matching cut in $G$. If $x$ and $y$ are nonadjacent, then assume $N(x)=\{x_1,x_2\}$. Since $G$ contains no triangles, then $x_1$ and $x_2$ are nonadjacent.  There are two cases to consider.  If $d(x_1)=2$, then let $u_1$ be another neighbor of $x_1$, and then $\{xx_2,x_1u_1\}$ is an $x$-$y$ matching cut.  If $d(x_1)=d(x_2)=3$, let $N(x_1)=\{x,u_1,u_2\}$ and $N(x_2)=\{x,v_1,v_2\}$. There are two cases to consider.  If $\{u_1,u_2\}\cap \{v_1,v_2\}\neq \emptyset$, assume $u_1=v_1$. Let $w,q$ be another neighbor of $u_2$ and $v_2$, respectively.  If $y\neq v_2$, then $\{xx_1,x_2u_1,v_2q\}$ is an $x$-$y$ matching cut.  Otherwise, $\{xx_2,x_1u_1,u_2w\}$ is an $x$-$y$ matching cut.  Assume $\{u_1,u_2\}\cap \{v_1,v_2\}=\emptyset$. Let $w,q$ be another neighbor of $u_1$ and $u_2$, respectively.  If $y=u_1$, then $\{xx_2,x_1u_1,u_2q\}$ is an $x$-$y$ matching cut.  Otherwise, $\{xx_2,x_1u_2,u_1w\}$ is an $x$-$y$ matching cut. 

For $d(x)=3$ (or $d(y)=3$), assume $N(x)=\{x_1,x_2,x_3\}$. Since the set of vertices with degree $3$ in $G$ forms an independent set, the neighbors of $x$ have degree at most two.  Since $G$ is $K_{2,3}$-free, there exists at least one vertex in $N(x)$ which has only one common neighbor $x$ with the others in $N(x)$. Without loss of generality, say $x_1$. Let $N(x_1)=\{x,s_1\},N(x_2)=\{x,s_2\}$ and $N(x_3)=\{x,s_3\}$ ($s_2=s_3$ is possible ).  If $x$ and $y$ are not adjacent, then $\{x_1s_1,x_2s_2,xx_3\}$ is an $x$-$y$ matching cut.  If $x$ and $y$ are adjacent, there are three cases to consider.  When $y=x_2$ (or $x_3$), we have $\{x_1s_1,xy,x_3s_3\}$ (or $\{x_1s_1,xy,x_2s_2\}$) is an $x$-$y$ matching cut.  When $y=x_1$ and $s_2=s_3$, if $d(s_2)=2$, then $\{xy\}$ is an $x$-$y$ matching cut; if $d(s_2)=3$, then assume $N(s_2)=\{x_2,x_3,p_1\}$, and then $\{xy,s_2p_1\}$ is an $x$-$y$ matching cut.  When $y=x_1$ and $s_2\neq s_3$, we have $\{xy,x_2s_2,x_3s_3\}$ is an $x$-$y$ matching cut.  Thus, $pd(G)=1$ by Theorem \[pd1\]. 

Let $G$ be a connected graph with $\Delta=3$. If the set of vertices with degree $3$ in $G$ forms an independent set, then deciding whether $pd(G)=1$ is solvable in polynomial time. 

We naturally put forward the following question. 

Let $G$ be a connected graph with $\Delta=3$. Is it true that deciding whether $pd(G)=1$ is solvable in polynomial time ? 

Hardness results for bipartite graphs
=====================================

In fact, by Corollary \[cor\], we know that it is $NP$-complete to decide whether $pd(G)=1$ for a general graph $G$. In this section, we will further show that given a bipartite graph $G$, deciding whether $pd(G)=1$ is $NP$-complete. 

Let $G$ be a simple connected graph.  We employ the idea used in [@M] to construct a new graph $G^*$. Let $G^*$ be a graph obtained from $G$ by replacing each edge by a $4$-cycle.  Then $G^*$ has two types of vertices: *old* vertices, which are vertices of $G$, and *new* vertices, which are not vertices of $G$. For example, for an edge $e=uv \in E(G)$, replace it by a 4-cycle $C_{e}=uxvyu$. Then $u,v$ are old vertices and $x,y$ are new vertices.  Observe that all new vertices of $G^*$ have degree two, and each edge of $G^*$ connects an old vertex to a new vertex.  Clearly, $G^*$ is a bipartite graph with one side of bipartition consisting only of vertices of degree $2$.

\[bipar\] Let $G$ be a simple connected graph.  Then $pd(G)=1$ if and only if $pd(G^*)=1$.

Suppose $pd(G^*)=1$. For any two vertices $x,y$ of $G$, $x,y$ are old vertices in $G^*$. By Theorem \[pd1\], there exists an $x$-$y$ matching cut $F$ in $G^*$. Then $F$ consists of pairs of matching edges in the same $4$-cycle.  Let $F'$ be the edge set obtained by replacing each pair of matching edges of $F$ in the same $4$-cycle by the edge to which the $4$-cycle corresponds in $G$. Then $F'$ is an $x$-$y$ matching cut in $G$.

Suppose $pd(G)=1$. Then for any two vertices $u,v$ of $G$, there is a $u$-$v$ matching cut.  We denote it by $F_{uv}$. Let $F$ be an edge subset of $E(G)$. Choose two matching edges from each $4$-cycle to which each edge of $F$ corresponds in $G^*$. Denote the edge set by $F^*$.

For any two vertices $x,y$ in $G^*$, if $x,y$ are old vertices, then $F^*_{xy}$ is an $x$-$y$ matching cut in $G^*$. If $x$ is an old vertex and $y$ is a new vertex, there are two cases to consider.  If $x,y$ are in the same 4-cycle, assume that the 4-cycle is $xyzwx$. We know $xz\in F_{xz}$ in $G$. Then $(F_{xz}\setminus \{xz\})^*\cup \{xy,zw\}$ is an $x$-$y$ matching cut in $G^*$. If $x,y$ are in different 4-cycles, say $C_1=xv_1uv_2x$ and $C_2=yz_1wz_2y$. If there are no $x$-$z_2$ paths in $G-F_{xz_1}$, then $F^*_{xz_{1}}$ is an $x$-$y$ matching cut in $G^*$. Otherwise, we know $z_1z_2\in F_{xz_1}$. Then $(F_{xz_1}\setminus \{z_1z_2\})^*\cup \{yz_2,wz_1\}$ is an $x$-$y$ matching cut in $G^*$. If $x,y$ are new vertices, there are two cases to consider.  If $x,y$ are in the same 4-cycle, assume that the 4-cycle is $\{uxvyu\}$. Then $F^*_{uv}$ is an $x$-$y$ matching cut in $G^*$. If $x,y$ are in different 4-cycles, say $C_1=u_1xu_2vu_1$ and $C_2=z_1yz_2wz_1$. Denote the component containing $u_1$ by $C$ and the remaining part by $\bar{C}$ in $G-F_{u_1u_2}$. If $\{z_1z_2\}\subseteq \bar{C}$, then $(F_{u_1u_2}\setminus \{u_1u_2\})^*\cup \{u_1v,u_2x\}$ is an $x$-$y$ matching cut in $G^*$. If $z_1 \in C$ and $z_2\in \bar{C}$, then $z_1z_2\in F_{u_1u_2}$. Then, $(F_{u_1u_2}\setminus \{u_1u_2,z_1z_2\})^*\cup \{u_1v,u_2x,z_1y,z_2w\}$ is an $x$-$y$ matching cut in $G^*$. If $\{z_1z_2\}\subseteq C$, then $(F_{u_1u_2}\setminus \{u_1u_2\})^*\cup \{u_1x,u_2v\}$ is an $x$-$y$ matching cut in $G^*$.

From the above Lemma \[bipar\], we can immediately get the following result. 

Given a bipartite graph $G$, deciding whether $pd(G)=1$ is $NP$-complete. 

[1]{}

X. Bai, R. Chang, X. Li, More on rainbow disconnection in graphs, arXiv:1810.09736 \[math. CO\]. 

X. Bai, Y. Chen, M. Ji, X. Li, Y. Weng, W. Wu, Proper disconnection in graphs, arXiv:1906.01832 \[math. CO\]. 

J.A. Bondy, U.S.R. Murty, Graph Theory, GTM $244$, Springer, $2008$.

G. Chartrand, S. Devereaux, T.W. Haynes, S.T. Hedetniemi, P. Zhang, Rainbow disconnection in graphs, [*Discuss.  Math.  Graph Theory*]{} **38**(2018), 1007–1021. 

A. Darmann, J. Döcker, On simplified $NP$-complete variants of Not-All-Equal 3-SAT and 3-SAT, arXiv:1908.04198 \[cs. CC\]. 

P. Li, X. Li, Monochromatic disconnection of graphs, arXiv:1901.01372 \[math. CO\]. 

P. Li, X. Li, Monochromatic disconnection: Erdös-Gallai-type problems and product graphs, arXiv:1904.08583 \[math. CO\]. 

A.M. Moshi, Matching cutsets in graphs, [*J. Graph Theory*]{} **13**(1989), 527–536. 

M. Patrignani, M. Pizzonia, The complexity of the matching-cut problem, Tech.  Report RT-DIA-35-1998, Dept.  Comput.  Sci.,  Univ.  di Roma Tre, 1998. 

T.J. Schaefer, The complexity of satisfiability problems, In Procceedings of the 10th annual ACM sympodium on Theory of Computing, pages 216–226, ACM, 1978. 

[^1]: Supported by NSFC No.11871034 and 11531011.