Finding $𝒅$-Cuts in Claw-Free Graphs

Assume $G$ has no independent set of size $t$. Let $k$ be the degeneracy of $G$, so $G$ has a subgraph of minimum degree at least $k$. Consider a $(k+1)$-colouring $c$ of $G$. As every colour class of $c$ is an independent set, we have $k+1\ge \frac{|V|}{t-1}$ and thus $k\ge \frac{|V|}{t-1}-1$. $◀$ Let $d\ge 1$ be an integer. A red-blue colouring of $G$ gives each vertex of $G$ either colour red or blue. A red-blue $d$-colouring of $G$ is a red-blue colouring where every vertex has at most $d$ neighbours of the other colour and both colours, red and blue, are used at least once. See Figure 1 for an example of a red-blue $1$-colouring (left figure) and a red-blue $3$-colouring (right figure). In our proofs, we use the following well-known observation; see e.g. [21].

Let $G$ be a graph with a red-blue $d$-colouring for some $d\ge 1$. We say that a set $S\subseteq V$ is monochromatic if all vertices in $S$ have the same colour.

We will also use the following observations, which can be readily seen.

Assume that each vertex in $S$ is incident to at most $d$ edges in $\delta (S)$. We will now construct a red-blue $d$-colouring of $G$, which, by Observation 6, gives that $G$ has a $d$-cut. We first colour every vertex in $S$ blue and recursively colour an uncoloured vertex blue if it has at least $d+1$ blue neighbours. Note that this takes $𝒪(|V|)$ time, as $|E|\le (2d+1)|V|/2$. We colour all remaining vertices of $G$ red. See also Figure 4.

Let $R$ and $B$ be the sets of red and blue vertices, respectively. Note that $S\subseteq B$. By construction, every vertex in $R$ has at most $d$ neighbours in $B$. As we assume that each vertex in $S$ is incident to at most $d$ edges in $\delta (S)$, each vertex in $S$ has at most $d$ neighbours in $R$. Since $\mathrm{\Delta }(G)\le 2d+1$ and each vertex in $B\setminus S$ has at least $d+1$ neighbours in $B$, each vertex in $B\setminus S$ has at most $d$ neighbours in $R$. Hence, every vertex in $B$ has at most $d$ neighbours in $R$. It remains to show that $R\ne \mathrm{\varnothing }$, or equivalently, that $B\ne V$, which we will do below.

Let $v_1,\mathrm{\dots },v_b$ denote the vertices in $B\setminus S$ in the order they are coloured blue. For an arbitrary $i\in [b]$, let $B^{\prime }:=S\cup \{v_1,\mathrm{\dots },v_i\}$. Recall that by construction, each vertex $v\in B^{\prime }\setminus S$ has at least $d+1$ neighbours in $B^{\prime }$ and at most $d$ neighbours not in $B^{\prime }$. So when we colour $v$ blue, that is, add $v$ to $B$, we lose at least $d+1$ edges with exactly one blue end-vertex and gain at most $d$ new edges with exactly one blue end-vertex. In other words, $|\delta (B^{\prime }\setminus \{v\})|\ge |\delta (B^{\prime })|+1$. This implies $|\delta (S)|\ge |\delta (B)|+(|B|-|S|)$, and thus $|\delta (S)|+|S|\ge |\delta (B)|+|B|$. We use this and our assumption that $|V|>|\delta (S)|+|S|$ to deduce that

and thus $B\ne V$. Hence, we obtained a red-blue $d$-colouring of $G$. $◀$ To prove the first part of Theorem 3, we prove a stronger statement in Theorem 10 and afterwards we show how Theorem 10 implies the first part of Theorem 3. For every positive integer $t$ and $\mathrm{\ell }$, we recall that $S_{1^t,\mathrm{\ell }}$ is the graph obtained from $K_{1,t+1}$ by replacing one edge with a path of length $\mathrm{\ell }$, see Figure 2. Note that $S_{1^t,\mathrm{\ell }}$ contains exactly $t+\mathrm{\ell }$ edges. In addition, $S_{1^t,1}$ is the graph $K_{1,t+1}$.

Let $d\ge 2$, $t\ge 2$ and $\mathrm{\ell }\ge 1$. Let $G$ be an $S_{1^t,\mathrm{\ell }}$-free graph. If $\mathrm{\Delta }=2$, then $G$ has a $d$-cut: take all edges between any vertex of $G$ and its neighbours. From now on, assume $3\le \mathrm{\Delta }\le \frac{t}{t-1}d+\frac{1}{t-1}$ and and $|V|>(d+1)\left(\frac{\mathrm{\Delta }{(\mathrm{\Delta }-1)}^{\mathrm{\ell }+1}-2}{\mathrm{\Delta }-2}\right)$.

We choose an arbitrary vertex $v$ of $G$ and let $S_0:=\{v\}$. For each $i\in [\mathrm{\ell }+1]$, we denote by $S_i$ the set of vertices which are at distance exactly $i$ from $v$ in $G$. Note that $|S_1|\le \mathrm{\Delta }$ and for each $i\in [\mathrm{\ell }]$, $|S_{i+1}|\le (\mathrm{\Delta }-1)|S_i|$. Thus,

Let $U$ be the set of vertices in $S_{\mathrm{\ell }}$ which are incident to at least $d+1$ edges in $\delta (S_{\mathrm{\ell }-1}\cup S_{\mathrm{\ell }})$. For each $u\in U$, we denote by $N_u$ the set of neighbours of $u$ not in $S_{\mathrm{\ell }-1}\cup S_{\mathrm{\ell }}$ and by $G_u$ the subgraph of $G$ induced on $N_u$.

We first show that $N_u$, for $u\in U$, has no independent set of size $t$. Suppose not. By the definition of $S_{\mathrm{\ell }}$, there is an induced path of length $\mathrm{\ell }$ between $v$ and $u$. Together with this path and the independent set in $N_u$, we can find $S_{1^t,\mathrm{\ell }}$ as an induced subgraph, a contradiction. Thus, $N_u$ has no independent set of size $t$.

For each $u\in U$, since $G_u$ has no independent set of size $t$, by Observation 5, $G_u$ has a subgraph $H_u$ whose minimum degree is at least

We remark that $H_u$ can be found in constant time as $|N_u|\le \mathrm{\Delta }-1$, which is a constant. Now, we let

Note that $S$ can be found in constant time as $|U|\le |S_{\mathrm{\ell }}|\le \mathrm{\Delta }{(\mathrm{\Delta }-1)}^{\mathrm{\ell }-1}$, which is a constant.

We are going to apply Lemma 9 to $S$. Since $t\ge 2$, we have $t\le 2(t-1)$, and therefore

To apply Lemma 9 to $S$, we first show that every vertex in $S$ is incident to at most $d$ edges in $\delta (S)$. By construction, this holds for every vertex in $S\setminus {\bigcup }_{u\in U}(N_u\cup \{u\})$. Let $u$ be a vertex in $U$ and let $w$ be a vertex in $N_u\cup \{u\}$. Note that $u$ and $w$ might be the same. Since the minimum degree of $H_u$ is at least

and $u$ is adjacent to every vertex in $N_u$, there are at least

neighbours of $w$ in $S$. Then $w$ is incident to at most

edges in $\delta (S)$. That is, $w$ is incident to at most $d$ edges in $\delta (S)$. Hence, every vertex in $S$ is incident to at most $d$ edges in $\delta (S)$.

We now show that $|V|>|S|+|\delta (S)|$. Since $S\subseteq {\bigcup }_{i=0}^{\mathrm{\ell }+1}{S}_i$, we have

Since every vertex in $S$ is incident to at most $d$ edges in $\delta (S)$, we have $|\delta (S)|\le d|S|$. Thus,

Hence, by Lemma 9, we can find a $d$-cut of $G$ in linear time. $◀$

We now show that Theorem 10 implies Theorem 3, which we recall below.

Let $G$ be a claw-free graph. If $\mathrm{\Delta }(G)=2$, then we can apply Theorem 10 directly. Assume $\mathrm{\Delta }(G)\ge 3$. Theorem 10 with $t=2$ and $\mathrm{\ell }=1$ implies the first part of Theorem 3. In order to see this, let $G$ be a claw-free graph with maximum degree $\mathrm{\Delta }(G)\le 2d+1$ and $|V|>4d^2(2d+1)$. As $2d+1=\frac{t}{t-1}d+\frac{1}{t-1}$ if $t=2$, we obtain $\mathrm{\Delta }(G)\le \frac{t}{t-1}d+\frac{1}{t-1}$. We also observe:

where the last inequality holds from the fact that $2d-1\ge d+1$ and the function $x{(x-1)}^2/(x-2)$ is increasing for $x\ge 3$. Hence, the conditions in Theorem 10 are satisfied, and we may conclude that $G$ has a $d$-cut, which can be found in linear time. $◀$

We now prove the second part of Theorem 3, which shows that the bound given in the first part of Theorem 3 is best possible. We slightly reformulate the statement as follows.

Let $T_1,\mathrm{\dots },T_k$ be pairwise disjoint cliques of size $r$. For each $i\in [k]$, let $\{A_i,B_i\}$ be a partition of $T_i$ such that $|A_i|=d+1$. Note that

Let $H$ be the graph obtained from $T_1\cup \mathrm{\cdots }\cup T_k$ by adding $k$ new vertices $v_1,\mathrm{\dots },v_k$ such that for each $i\in [k]$, $N_H(v_i)$ is equal to $B_i\cup A_{i+1}$ where $A_{k+1}:=A_1$, see Figure 5. Note that $H$ has $rk+k=(r+1)k$ vertices.

We first show that $H$ is claw-free and $r$-regular. Let $i$ be an arbitrary integer in $[k]$. Since the neighbourhood of $v_i$ is the disjoint union of two cliques $B_i$ and $A_{i+1}$, $H$ has no claw centred at $v_i$. Note further that $v_i$ has degree $r$. Consider now a vertex $v$ in $T_i$. The neighbourhood of $v$ consists of all other vertices in $T_i$ and some vertex $v_j$, where $j\in \{i-1,i,k\}$. Hence, $v$ has degree $(r-1)+1=r$ and since $T_i$ is a clique, $H$ has no claw centred at $v$. We conclude that $H$ is claw-free and $r$-regular.

It remains to show that $H$ has no $d$-cut. Note that in any red-blue $d$-colouring of $H$, $T_i$, for $i\in [k]$, is monochromatic by Observation 8, since it is a clique of size at least $2d+2$. We claim that

is monochromatic in every red-blue $d$-colouring of $H$. Suppose for a contradiction that $H$ has a red-blue $d$-colouring where $T$ is not monochromatic. Then there exists $j\in [k]$ such that $T_j$ and $T_{j+1}$ have different colours, where $T_{k+1}:=T_1$. Without loss of generality, assume that $T_j$ is coloured red. Consequently, $T_{j+1}$ is coloured blue. Since $v_j$ has at least $d+1$ red neighbours in $B_j$, it is coloured red. However, $v_j$ has $d+1$ blue neighbours in $A_{j+1}$, contradicting the fact that we considered a red-blue $d$-colouring. Hence, if $H$ has a red-blue $d$-colouring, then $T$ is monochromatic.

Thus, if $H$ has a red-blue $d$-colouring, then $T$ is monochromatic and hence, $v_i$, for $i\in [k]$, is coloured the same as $T$ since $v_i$ has at least $2d+2$ neighbours in $T$. Therefore, there is no red-blue $d$-colouring of $H$. By Observation 6, $H$ has no $d$-cut. $◀$

Let $H$ be the graph in Theorem 11, with respect to the same integers, and let $H^{\prime }:=H_{d,k,r}$. Note that

Since $H$ is $r$-regular and $w_1,\mathrm{\dots },w_k$ have pairwise disjoint neighbourhoods, each of $w_1,\mathrm{\dots },w_k$ has degree $d+2$, and the other vertices have degree either $r$ or $r+1$.

We show that $H^{\prime }$ is claw-free. Suppose that $H^{\prime }$ has a claw $K$ centred at a vertex $c$. Since $H$ is claw-free, $K$ contains $w_i$ for some $i\in [k]$. As $N_{H^{\prime }}(w_i)$ is a clique, $c\ne w_i$. So $N_{H^{\prime }}(c)$ is the union of two cliques, contradicting that $K$ is a claw. Hence, $H^{\prime }$ is claw-free.

It remains to show that $H^{\prime }$ has no $d$-cut. By Observation 6, $H^{\prime }$ has a $d$-cut if and only if $H^{\prime }$ has a red-blue $d$-colouring. By Theorem 11, we know that $V(H)$ is monochromatic in every red-blue $d$-colouring. Further, $w_i$, for $i\in [k]$, has $d+2$ neighbours in $H$. Thus, by Observation 7, $w_i$ is coloured the same as $V(H)$. This implies that $V(H^{\prime })$ is monochromatic in every red-blue $d$-colouring and hence $H^{\prime }$ has no red-blue $d$-colouring. It follows that $H^{\prime }$ has no $d$-cut. $◀$

We are now ready to prove the remaining part of Theorem 4, which we restate below.

We reduce from NAE $3$-Sat $0$-$1$. Let $\varphi$ be an instance of NAE $3$-Sat $0$-$1$ with variables $x_1,\mathrm{\dots },x_n$ and clauses $C_1,\mathrm{\dots },C_m$. In the following, we construct an instance $G$ of $d$-Cut which is claw-free and has maximum degree $2d+3$. For each $\mathrm{\ell }\in [n]$, let $k_{\mathrm{\ell }}$ be the number of occurrences of $x_{\mathrm{\ell }}$ in $\varphi$ and let $F_{\mathrm{\ell }}$ be a copy of $H_{d,k_{\mathrm{\ell }},2d+2}$. We say that a vertex of $F_{\mathrm{\ell }}$ is free if it has degree $d+2$ in $F_{\mathrm{\ell }}$. Note that $F_{\mathrm{\ell }}$ has exactly $k_{\mathrm{\ell }}$ free vertices. We remark that these free vertices will play the role of variable vertices for $x_{\mathrm{\ell }}$.

For each clause $C_i=({\overline{x}}_{i_1}\vee x_{i_2}\vee x_{i_3})$, for $i\in [m]$, we add two disjoint cliques $D_{i,1}$ of size $d$ and $D_{i,2}$ of size $d+1$. In addition, we add a vertex $c_i$. We let $D_i:=D_{i,1}\cup D_{i,2}$ and call $D_i\cup \{c_i\}$ a clause gadget. We add all edges between $D_{i,1}$ and $D_{i,2}$ and between $c_i$ and $D_{i,1}$. For each $j\in [3]$, we choose some free vertex of $F_{i_j}$ and call this vertex $w_{i_j}$. We add edges between $w_{i_1}$ and each vertex in $D_{i,1}\cup \{c_i\}$, edges between $w_{i_2}$ and each vertex in $D_{i,2}$, and we also add an edge between $c_i$ and $w_{i_3}$, see Figure 7. We choose these free vertices in such a way that every free vertex has neighbours in exactly one clause gadget. This is possible as, for every $\mathrm{\ell }\in [n]$, $F_{\mathrm{\ell }}$ has $k_{\mathrm{\ell }}$ free vertices and $x_{\mathrm{\ell }}$ appears $k_{\mathrm{\ell }}$ times in $\varphi$. Let $G$ be the resulting graph.

We first show that $G$ is a claw-free graph of maximum degree $2d+3$. Let $\mathrm{\ell }$ be an arbitrary integer in $[n]$. Let $v\in V(F_{\mathrm{\ell }})$ be a vertex that is not free. Then, by Lemma 13, $v$ has degree at most $2d+3$ and further, since $v$ has neighbours only in $F_{\mathrm{\ell }}$, $G$ has no claw centred at $v$. Let $w$ be a free vertex of $F_{\mathrm{\ell }}$. Recall that $w$ has a neighbour in a clause gadget $D_i\cup \{c_i\}$ for some $i\in [m]$. Note that $w$ has degree at most $(d+2)+(d+1)=2d+3$ since it has $d+2$ neighbours within $F_{\mathrm{\ell }}$ and at most $d+1$ neighbours in $D_i\cup \{c_i\}$. In addition, the neighbours of $w$ in $D_i\cup \{c_i\}$ form a clique of size $1$ or $d+1$. Thus, the neighbourhood of $w$ in $G$ is the union of this clique in $D_i\cup \{c_i\}$ and some clique in $F_{\mathrm{\ell }}$, so $G$ has no claw centred at $w$.

Finally, we consider the clause gadget $D_i\cup \{c_i\}$. Recall that $c_i$ is a fixed vertex with neighbourhood $D_{i,1}\cup \{w_{i_1},w_{i_3}\}$. Thus, it has degree $d+2$. Since $w_{i_1}$ is complete to $D_{i,1}$, the neighbourhood of $c_i$ is the union of two cliques. Hence, the vertex $c_i$ is not the centre of a claw of $G$. Let $u$ be a vertex in $D_{i,1}$. The closed neighbourhood of $u$ is $D_i\cup \{c_i,w_{i_1}\}$, which is the union of the two cliques $D_{i,1}\cup \{c_i,w_{i_1}\}$ and $D_{i_2}$. Hence, $u$ is not the centre of a claw in $G$. Since $|D_i|=2d+1$, $u$ has degree $2d+2$. Now, let $u^{\prime }$ be a vertex in $D_{i,2}$. The closed neighbourhood of $u^{\prime }$ is $D_i\cup \{w_{i_2}\}$, which is the union of the two cliques $D_i$ and $\{w_{i_2}\}$. So $u^{\prime }$ is not the centre of a claw in $G$. Again, as $|D_i|=2d+1$, the vertex $u^{\prime }$ has degree $2d+1$. It follows that $G$ is a claw-free graph of maximum degree at most $2d+3$.

We show that $G$ has a $d$-cut if and only if $\varphi$ has an NAE-satisfying assignment with both a true and a false variable. By Observation 6, this is equivalent to showing that $G$ has a red-blue $d$-colouring if and only if $\varphi$ has an NAE-satisfying assignment with both a true and a false variable.

We assume first that $G$ has a red-blue $d$-colouring and show that $\varphi$ has an NAE-satisfying assignment with both a true and a false variable. Recall that by Lemma 13, $F_{\mathrm{\ell }}$ is monochromatic for each $\mathrm{\ell }\in [n]$. We set a variable $x_{\mathrm{\ell }}$ to true if $F_{\mathrm{\ell }}$ is coloured blue and to false otherwise.

We first show that the resulting assignment contains both a true and a false variable. Suppose for a contradiction that this is not the case. We may assume without loss of generality that all variables are true. This implies that for every $\mathrm{\ell }\in [n]$, $F_{\mathrm{\ell }}$ is coloured blue. Note that $D_i$, for $i\in [m]$, is a clique of size $2d+1$ and thus monochromatic by Observation 8. As $w_{i_2}\in F_{i_2}$, it is coloured blue. Further, $w_{i_2}$ has $d+1$ neighbours in $D_{i,2}\subseteq D_i$. Hence, since $D_{i,2}$ is monochromatic, $D_{i,2}$ is coloured blue. It follows that $D_{i,1}$ is blue as well and, since $c_i$ has $d+1$ blue neighbours in $D_{i,1}\cup \{w_{i_1}\}$, it is coloured blue. Thus, the whole graph is coloured blue, contradicting the fact that we considered a red-blue $d$-colouring. Therefore, the assignment contains both a true and a false variable.

We now show that the assignment is NAE-satisfying for $\varphi$. Suppose for a contradiction that the assignment is not NAE-satisfying. Then there exists a clause $C_i=({\overline{x}}_{i_1}\vee x_{i_2}\vee x_{i_3})$, for some $i\in [m]$, such that all literals have the same value. Note that this implies that both $x_{i_2}$ and $x_{i_3}$ take the opposite value of $x_{i_1}$. Without loss of generality, assume that $x_{i_1}$ is true and $x_{i_2}$ and $x_{i_3}$ are both false. That is, $w_{i_1}$ is coloured blue while $w_{i_2}$ and $w_{i_3}$ are coloured red. Recall that $D_i$ is monochromatic. Since $w_{i_2}$ has $d+1$ neighbours in $D_{i,2}$, $D_i$ is coloured the same as $w_{i_2}$ and is thus coloured red. This implies that the blue vertex $w_{i_1}$ has $d$ red neighbours in $D_{i,1}$, so its neighbour $c_i$ is coloured blue. However, as $w_{i_3}$ is coloured red, $c_i$ has $d+1$ red neighbours in $D_{i,1}\cup \{w_{i_3}\}$, contradicting the fact that we considered a red-blue $d$-colouring. Hence, the assignment is NAE-satisfying for $\varphi$.

For the other direction, we now assume that $\varphi$ has an NAE-satisfying assignment with both a true and a false variable. We construct a red-blue $d$-colouring of $G$ as follows. For each $\mathrm{\ell }\in [n]$, we colour $F_{\mathrm{\ell }}$ blue if it corresponds to a true variable and red otherwise. For each $i\in [m]$, we colour $D_i$ the same as $w_{i_2}$. In addition, we colour $c_i$ the same as $w_{i_1}$.

We show that this colouring is indeed a red-blue $d$-colouring of $G$. Note first that since the assignment contains both a true and a false variable, we have both red and blue vertices. It remains to show that every vertex has at most $d$ neighbours of the other colour. Let $\mathrm{\ell }$ be an arbitrary integer in $[n]$. Note that every vertex of $F_{\mathrm{\ell }}$ which is not a free vertex has no neighbour of the other colour. Let $w$ be a free vertex of $F_{\mathrm{\ell }}$. Recall that there is exactly one clause $C_i$, for $i\in [m]$, such that $w$ is adjacent to the corresponding clause gadget $D_i$. That is, $w\in \{w_{i_1},w_{i_2},w_{i_3}\}$. We distinguish between these cases:

• $\mathrm{■}$

  If $w=w_{i_3}$, then it has one neighbour outside of $F_{\mathrm{\ell }}$ and thus at most one neighbour of the other colour.

• $\mathrm{■}$

  If $w=w_{i_2}$, then, by construction, it has no neighbour of the other colour.

• $\mathrm{■}$

  If $w=w_{i_1}$, then it has $d+1$ neighbours outside of $F_{\mathrm{\ell }}$ and, by construction, at least one of them, namely $c_i$, has the same colour as $w$.

Thus, $w$ has at most $d$ neighbours of the other colour.

Now, let $u$ be a vertex in $D_i$. If $u\in D_{i,2}$, then its closed neighbourhood is $D_i\cup \{w_{i_2}\}$, which is monochromatic by construction. Thus, $u$ has no neighbour of the other colour. If $u\in D_{i,1}$, then, since $D_i$ is monochromatic, the only neighbours of $u$ which may be coloured with the other colour are $w_{i_1}$ and $c_i$. Since $d\ge 2$, it follows that $u$ has at most $d$ neighbours of the other colour. Thus, we may assume that $u=c_i$. Recall that the neighbourhood of $c_i$ is $D_{i,1}\cup \{w_{i_1},w_{i_3}\}$ and that $c_i$ is coloured the same as $w_{i_1}$. Assume without loss of generality that $c_i$ is coloured blue. Suppose for a contradiction that $c_i$ has at least $d+1$ red neighbours. That is, $D_{i,1}$ and $w_{i,3}$ are coloured red. Since $D_i$ is monochromatic by construction, this implies that $D_{i,2}$ and thus $w_{i,2}$ are coloured red as well. Hence, $w_{i,2}$ and $w_{i,3}$ are both coloured red, while $w_{i,1}$ is coloured blue, a contradiction to the assumption that the assignment is NAE-satisfying. Thus, $c_i$ has at most $d$ neighbours of the other colour. Hence, the colouring is indeed a red-blue $d$-colouring of $G$. This completes the proof. $◀$ We remark that for every $\mathrm{\Delta }>2d+3$, $d$-Cut is still NP-complete on claw-free graphs with maximum degree $\mathrm{\Delta }$: after replacing each $F_{\mathrm{\ell }}$ as a copy of $H_{d,k_{\mathrm{\ell }},\mathrm{\Delta }-1}$, instead of $H_{d,k_{\mathrm{\ell }},2d+2}$, the same hardness proof works.