Colouring Probe $H$-Free Graphs

Král et al. [54] showed that if $H$ is a (not necessarily proper) induced subgraph of $P_4$ or $P_3+P_1$, where $P_t$ denotes the path on $t$ vertices, then Colouring on $H$-free graphs is solvable in polynomial time; otherwise, it is $\mathrm{𝖭𝖯}$-complete. For $k$-Colouring, the complexity status on $H$-free graphs has not been resolved yet. For every $k\ge 3$, $k$-Colouring for $H$-free graphs is $\mathrm{𝖭𝖯}$-complete if $H$ has a cycle [37] or an induced claw [50, 56]. However, the remaining case where $H$ is a linear forest (disjoint union of paths) has not been settled yet. For $P_t$-free graphs, the cases $k\le 2$, $t\ge 1$ (trivial), $k\ge 3$, $t\le 5$ [49], $k=3$, $6\le t\le 7$ [9] and $k=4$, $t=6$ [28, 29] are polynomial-time solvable and the cases $k=4$, $t\ge 7$ [51] and $k\ge 5$, $t\ge 6$ [51] are $\mathrm{𝖭𝖯}$-complete. The cases $k=3$ and $t\ge 8$ are still open, despite some evidence that these cases are polynomial-time solvable due to a quasi-polynomial-time algorithm [60]. We refer to the survey [41] and some later articles [25, 26, 48, 53] for results on $k$-Colouring for $H$-free graphs if $H$ is a disconnected linear forest, and to [52] for the most recent results on Colouring for $(H_1,H_2)$-free graphs, for which also still many cases remain open.

In this article, we aim to further our understanding of the complexity of Colouring and $k$-Colouring by studying probe graphs. Probe graphs are used to model graphs for which the global structure is known (e.g. $H$-freeness). However, we only know the complete set of neighbours for some vertices of a probe graph $G$. These vertices are the probes of $G$. The other vertices are the non-probes of $G$ and form an independent set in $G$, as we do not know which of them are adjacent to each other. We only know that there exists a “certifying” set $F$ of edges on the non-probes such that $G+F$ exhibits the global structure (e.g. being $H$-free). In particular, the subgraph of $G$ induced by the set of probes already has this global structure (e.g. is $H$-free). The notion of probe graphs was introduced by Zhang et al. [64] in genome research to make a genome mapping process more efficient.

Formally, for a graph class $𝒢$, the class ${𝒢}_p$ consists of all graphs $G$ that can be modified into a graph from $𝒢$ by adding some edges between an independent set $N$ of $G$. If for a graph in ${𝒢}_p$, the sets $P$ and $N=V\setminus P$ are given, then we speak of a partitioned probe graph. Hence, a partitioned probe $H$-free graph $(G,P,N)$ consists of a graph $G=(V,E)$, together with a set $P\subseteq V$ of probes and an independent set $N=V\setminus P$ of non-probes, such that $G+F$ is $H$-free for some edge set $F\subseteq \left(\genfrac{}{}{0pt}{}{N}{2}\right)$. We note that an $H$-free graph itself is also a (partitioned) probe $H$-free graph, namely with $P=V$ and $N=\mathrm{\varnothing }$. Hence, for every graph $H$, the class of (partitioned) probe $H$-free graphs contains the class of $H$-free graphs. Consequently, any $\mathrm{𝖭𝖯}$-completeness results for $H$-free graphs immediately carry over to partitioned probe $H$-free graphs. However, it also leads to the following research question:
If an $\mathrm{𝖭𝖯}$-complete problem $\mathrm{\Pi }$ is polynomial-time solvable on $H$-free graphs for some graph $H$, is $\mathrm{\Pi }$ also polynomial-time solvable on (partitioned) probe $H$-free graphs?

To investigate our research question, we consider Colouring and $k$-Colouring for (partitioned) probe $H$-free graphs. For some graphs $H$, such as $H=P_4$ [22], probe $H$-free graphs can be recognized in polynomial time. However, for most graphs $H$, including $H=P_5$, the recognition of probe $H$-free graphs and the distinction between probes and non-probes are open problems. Hence, we usually require the sets of probes $P$ and non-probes $N$ to be part of the input, i.e., we must consider partitioned probe $H$-free graphs. Note that we can colour a probe $H$-free graph $G$ with one extra colour (assigned to each vertex in $N$) than the number of colours used for $G[P]$. The challenge is to determine if we need that extra colour.

So far, most previous work on probe graphs focused on characterising and recognising classes of probe graphs [42, 22, 20, 4, 43, 5, 55]. However, recently, the first systematic studies of optimisation problems on partitioned probe $H$-free graphs were undertaken. Brettell et al. [15] considered Vertex Cover on partitioned probe $H$-free graphs and Dabrowski et al. [31] did the same for Matching Cut and some of its variants. A takeaway from [15, 31] is that determining the complexity of Vertex Cover for (partitioned) probe $P_5$-free graphs seems challenging, whereas Matching Cut is $\mathrm{𝖭𝖯}$-complete on partitioned probe $P_5$-free graphs, even though they are both polynomial-time solvable on $P_5$-free graphs [58, 38].

Helpful for algorithmic studies as [15, 31] is that probe graphs inherit some properties from the graph class they are based on. This is also true when studying Colouring. For example, Golumbic and Lipshteyn [42] proved that probe chordal graphs are perfect. Hence, we obtain that Colouring is polynomial-time solvable for probe chordal graphs, as Colouring is so for perfect graphs [45, 46]. In 2012, Chandler et al. [21] conjectured that this holds even for Colouring on partitioned probe perfect graphs. Moreover, the following is known:

Hence, as $𝒢\subseteq {𝒢}_p$ holds for every graph class $𝒢$, we obtain that a graph class $𝒢$ has bounded mim-width (clique-width) if and only if ${𝒢}_p$ has bounded mim-width (clique-width). However, if the yes-instances for some problem $\mathrm{\Pi }$ in $𝒢$ have bounded width, this may no longer hold for the yes-instances for $\mathrm{\Pi }$ in ${𝒢}_p$. If we can still solve $\mathrm{\Pi }$ on ${𝒢}_p$, this means there might be a deeper reason for the polynomial-time behaviour of $\mathrm{\Pi }$ on $𝒢$. We will also research this.

As mentioned, we focus on Colouring and $k$-Colouring for probe $H$-free graphs. Our first result is a full dichotomy of Colouring on partitioned probe $H$-free graphs (for two graphs $G_1$ and $G_2$, we write $G_1{\subseteq }_i{G}_2$ if $G_1$ is an induced subgraph of $G_2$).

By Theorem 2, Colouring is $\mathrm{𝖭𝖯}$-complete for partitioned probe $3P_1$-free graphs, while Colouring is even polynomial-time solvable on $(P_3+P_1)$-free graphs [54]. It is known that the class of $H$-free graphs has bounded mim-width [13] if and and only if it has bounded clique-width (see e.g. [33]) if and only if $H$ is an induced subgraph of $P_4$. Hence, Theorem 2 also implies, together with Proposition 1, that Colouring on (not necessarily partitioned) probe $H$-free graphs is solvable in polynomial time exactly when the mim-width or clique-width is bounded. In fact, we apply Proposition 1 to show the first part of Theorem 2, while for the second part we modify a known hardness reduction for Colouring [6]; see Section 3.

Our second result is a full dichotomy for $3$-Colouring on partitioned probe $P_t$-free graphs:

In Section 4 we prove the polynomial part of Theorem 3 by giving our main result: a polynomial-time algorithm for $3$-Colouring for partitioned probe $P_5$-free graphs. The class of $P_5$-free graphs has been extensively studied for many well-known graph problems, yielding polynomial-time algorithms not only for $k$-Colouring for any $k\ge 1$ [49], but also Vertex Cover [58], Feedback Vertex Set [1], Independent Feedback Vertex Set [8] and very recently, Odd Cycle Transversal [2], or more generally, Maximum Partial List $H$-Coloring for every fixed graph $H$ [57]. Our polynomial-time result for $3$-Colouring on partitioned probe $P_5$-free graphs is the first result that generalizes a known polynomial-time result for a (classical) graph problem on $P_5$-free graphs to partitioned probe $P_5$-free graphs.

In Section 5 we prove the second part of Theorem 3. In fact, we show that $3$-Colouring is $\mathrm{𝖭𝖯}$-complete even on partitioned probe $(P_6,2P_3,3P_2)$-free graphs. In contrast, $3$-Colouring is polynomial-time solvable even on $P_7$-free graphs [9] and $s{P}_2$-free graphs for all $s\ge 1$ [32].

In Section 6, we point out many natural directions for future research. In particular, we determine all (disconnected) graphs $H$ for which $3$-Colouring on probe partitioned $H$-free graphs is still open and solve one such open case, namely when $H=P_3+s{P}_1$. Moreover, we consider $k$-Colouring for $k\ge 4$ and solve one open case, namely when $H=P_2+s{P}_1$ for $s\ge 1$, by proving that for every $s\ge 0$, all probe $(P_2+s{P}_1)$-free graphs are $(s+1)P_2$-free.

As evidenced by the $C_5$, there are $P_5$-free graphs that are not perfect, and there exist three different proofs for showing that $3$-Colouring is polynomial-time solvable on $P_5$-free graphs. As discussed below, these proofs are not applicable to probe $P_5$-free graphs, even though two of them provide good starting points.

First, in the proof of Brettell et al. [14], it was shown that $k$-colourable $P_5$-free graphs have bounded mim-width for all $k\ge 1$, directly implying that $k$-Colouring becomes polynomial-time solvable [17]. However, bipartite graphs are even $2$-colourable and readily seen to be even probe $2P_2$-free (as shown below explicitly for paths) while already chordal bipartite graphs have not only unbounded mim-width [12] but even unbounded sim-width [10]. This also shows that probe $3$-colourable $P_5$-free graphs, which have bounded mim-width due to Proposition 1, are only a small subclass of the class of $3$-colourable probe $P_5$-free graphs.

Second, in the proof of Randerath, Schiermeyer and Tewes [62], a connected $3$-colourable $P_5$-free graph is shown to have a dominating set $D$ of constant size. By precolouring $D$ in every possible way, polynomially many instances of $2$-List Colouring (i.e., where all lists of admissible colours have size $2$) are obtained. As $2$-List Colouring can be formulated as $2$-SAT, it is polynomial-time solvable [36]. This approach fails for probe $P_5$-free graphs. To see this, let $G$ be a path $u_1{u}_2\mathrm{\dots }{u}_{2n}$. Let $P=\{u_1,u_3,\mathrm{\dots },u_{2n-1}\}$ and $N=\{u_2,u_4,\mathrm{\dots },u_{2n}\}$. Note that $P$ and $N$ are independent. Hence, making $N$ a clique yields a split graph, which is $2P_2$-free, so $G$ is even probe $2P_2$-free. However, for large $n$, $G$ has no small dominating set.

Finally, in the proof of Woeginger and Sgall [63], it is first shown that every $(C_3,P_5)$-free graph $G$ is $3$-colourable. Next, the case where $G$ contains at least one triangle $C$ (which may not be dominating) is considered. After colouring $C$, the following rule is applied exhaustively: whenever a vertex $v$ has two neighbours not coloured alike, give $v$ the third colour. Afterwards, it is again shown that an instance of $2$-List Colouring is obtained. Also this approach does not work for probe $P_5$-free graphs due to their more intricate structure. By extending the arguments as in [63], we can show that even all $C_3$-free probe $P_5$-free graphs, which include all (probe) $(C_3,P_5)$-free graphs, are $3$-colourable (see Section 4). However, $C_3$-free probe $P_5$-free graphs form only a small subclass of $3$-colourable probe $P_5$-free graphs.

As we explain below, our proof for partitioned probe $P_5$-free graphs turns out to be substantially more involved than the second and third proofs for $P_5$-free graphs and does not rely on the boundedness of some width parameter.

First, if all connected components of the subgraph induced by the probes are bipartite, we can colour the probes with colours $1$ and $2$ and use colour $3$ for the non-probes (as the non-probes form an independent set). Next, we show that at most one connected component $K$ of the subgraph induced by the set of probes can be non-bipartite. Then, by $P_5$-freeness, we find that $K$ has a short odd cycle $C$. The fact that in general, $C$ is not a dominating cycle of the graph causes several complications. To overcome these complications, we branch on the colours of $C$ and then just like [63], we try to extend the colouring as much as possible using propagation rules, with the aim to reduce eventually to polynomially many instances of $2$-List Colouring. We show that the latter is possible via (i) a new decomposition of probe $P_5$-free graphs, which carefully takes into account the fact that we do not know the missing edges between the non-probes that make the graph $P_5$-free (as illustrated in Figure 3) and (ii) an adaptation of the standard 2-SAT formula for $2$-List Colouring.

Let the SAT formula $ℱ$ in conjunctive normal form have variables $x_v^i$ for every uncoloured vertex $v\in V(G)$ and every $i\in L(v)$, and clauses

• $\mathrm{■}$

  ${\bigvee }_{i\in L(v)}{x}_v^i$ for every uncoloured vertex $v$ (i.e., if $L(v)=\mathrm{\varnothing }$, then $ℱ$ is not satisfiable) and

• $\mathrm{■}$

  ${\overline{x}}_u^i\vee {\overline{x}}_v^i$ for every $uv\in E(G)$ with uncoloured vertices $u$ and $v$ and $i\in L(u)\cap L(v)$.

According to the assumptions $ℱ$ is a 2-SAT formula. By construction, there is a $k$-colouring of $G$ that is an extension of $\psi$ if and only if $ℱ$ is satisfiable. This completes the proof since deciding the satisfiability of a 2-SAT formula is possible in polynomial time [3]. $◀$

Let $G=(V,E)$ be a $C_3$-free probe $P_5$-free graph. Let $P$ be the set of probes and $N=V\setminus P$ be the set of non-probes, so $N$ is an independent set. By definition, there exists a set $F$ of edges with both end-vertices in $N$ such that $G+F$ is $P_5$-free. We may assume without loss of generality that $G$ is connected, as otherwise we consider every connected component of $G$ separately.

If $G[P]$ is bipartite, then we colour $G[P]$ with colours $1$ and $2$, and as $N$ is independent, we can use colour $3$ for the vertices of $N$. Now suppose that $G[P]$ is not bipartite. This means that $G[P]$ has an odd cycle $C$. As $G$ is $C_3$-free and probe $P_5$-free, $G[P]$ must be $(C_3,P_5)$-free. Hence, $C$ has length $5$. Let $V(C)=\{v_1,\mathrm{\dots },v_5\}$ in that order. We will now use, with a little bit of extra care, the same arguments as in [63].

We first claim that every vertex not on $C$ has a neighbour on $C$. Else, as $G$ is connected, there exists a vertex $u\in V\setminus V(C)$ that is anti-complete to $C$ and that has a neighbour $v$ that is adjacent to at least one vertex on $C$, say $v{v}_1\in E$. If $uv{v}_1{v}_2{v}_3$ is an induced $P_5$ in $G$, then $uv{v}_1{v}_2{v}_3$ is also an induced $P_5$ in $G+F$. The reason is that $F$ contains no edge that is incident with a vertex from $\{v_1,v_2,v_3\}$, because $v_1,v_2,v_3$ all belong to $P$. As $G$ is $C_3$-free and $G+F$ is $P_5$-free, this means that $v$ must be adjacent to $v_3$ in $G$. By applying the same arguments on the path $uv{v}_3{v}_4{v}_5$, we find that $v$ must be adjacent to $v_5$ in $G$ as well. However, now $v,v_1,v_5$ form a triangle in $G$, contradicting the $C_3$-freeness of $G$.

We now claim that every vertex not on $C$ has exactly two neighbours $v_i$ and $v_{i+2}$ on $C$ for some $i\in \{1,\mathrm{\dots },5\}$, where we write $v_6:=v_1$ and $v_7:=v_2$. Let $v\in V\setminus V(C)$. By the above, $v$ has a neighbour on $C$, say $v$ is adjacent to $v_1$. Recall that $F$ does not contain any edges incident to vertices of $C$, as $V(C)\subseteq P$. Hence, if $v{v}_1{v}_2{v}_3{v}_4$ is an induced $P_5$ in $G$, then $v{v}_1{v}_2{v}_3{v}_4$ is also an induced $P_5$ in $G+F$. As $G$ is $C_3$-free and $G+F$ is $P_5$-free, this means that $v$ is either adjacent to $v_3$ (take $i=1$) or to $v_4$ (take $i=4$). Due to the above, we can decompose $V$ as

where for $i\in \{1,\mathrm{\dots },5\}$, the set $V_{i,i+2}$ consist of all vertices of $V\setminus C$ whose neighbours on $C$ are exactly $v_i$ and $v_{i+2}$. We give $v_1,v_2,v_3,v_4,v_5$ colours $1,2,1,2,3$, respectively. Moreover, we colour all the vertices of $V_{1,3}$, $V_{2,4}$, $V_{3,5}$, $V_{4,1}$ and $V_{5,2}$ with colours $2,1,2,3,1$, respectively. As $G$ is $C_3$-free, the five sets $V_{i,i+1}$ are all independent. Therefore, the only potential conflicts could be between vertices from $V_{1,3}$ and $V_{3,5}$, which are all coloured $2$, or between vertices from $V_{2,4}$ and $V_{5,2}$, which are all coloured $1$. However, the former vertices are all incident to $v_3$, and thus form an independent set in $G$, and similarly, the latter vertices are all adjacent to $v_2$, and thus als form an independent set in $G$. We conclude that we have indeed constructed a $3$-colouring of $G$, completing the proof. $◀$ We are now ready to show the main result of our paper, which we prove in the way as outlined at the end of Section 1.

Let $(G,P,N)$ be a partitioned probe $P_5$-free graph. We may assume that $G$ is connected; otherwise, we execute the given algorithm for every connected component of $G$. Let $F\subseteq \left(\genfrac{}{}{0pt}{}{N}{2}\right)$ be such that $G+F$ is $P_5$-free. We define $F$ only for verifying correctness; the polynomial-time algorithm does not use $F$. If $G$ is $P_5$-free, then it is possible in polynomial time to determine whether $G$ is 3-colourable [49]. Therefore, we may assume that $G$ is not $P_5$-free and, in particular, $|N|\ge 2$ and $|F|\ge 1$. We may also assume that $G$ does not contain a clique of order at least $4$; otherwise, $G$ is not $3$-colourable. Let $K_1,\mathrm{\dots },K_t$ be the connected components of $G[P]$ that contain at least one edge. We may assume at least one such connected component exists; else $G$ is bipartite with partite sets $P$ and $N$, and thus clearly 3-colourable in polynomial time.

We begin by proving two claims that describe the structure of edges between $K_1,\mathrm{\dots },K_t$ and $N$.

Let $v\in N$ be neither complete nor anticomplete to $K_i$. Suppose that $v$ has a neighbour in $K_j$, where $j\ne i$. It suffices to prove that $v$ is complete to $K_j$. Assume, for a contradiction, that $w\in V(K_j)$ is not adjacent to $v$. By assumption, there exists $u\in V(K_i)$ that is not adjacent to $v$. A shortest $u$-$v$-path with internal vertices in $K_i$ followed by a shortest $v$-$w$-path with internal vertices in $K_j$ is induced in $G+F$ and has length at least 4; see Figure 1. Since such a path exists, there is an induced $P_5$ in $G+F$, a contradiction. $\mathrm{⊲}$

If $K_1,\mathrm{\dots },K_t$ are all bipartite, then $G$ is clearly 3-colourable, since $N$ is independent in $G$. Therefore, we may assume that $t\ge 1$ and $K_1$ is not bipartite. This implies that $K_1$ contains an induced odd cycle and, since $K_1$ is $P_5$-free because of $V(K_1)\subseteq P$, such a cycle has length $3$ or length $5$. We now pick an induced odd cycle $C$ in $K_1$ as follows. If $K_1$ contains an induced $C_5$, then let $C$ be any such $C_5$. If $K_1$ does not contain an induced $C_5$, but contains an induced $C_3$ that dominates $K_1$, then let $C$ be any such $C_3$. Otherwise, we pick $C$ to be an arbitrary $C_3$. Note that computing $C$ is possible in polynomial time.

If a single vertex of $V(G)\setminus C$ dominates $C$, then $G$ is clearly not 3-colourable. Hence, we may assume from here that this is not the case. This fact (that we often use implicitly) has important implications. In particular, no vertex of $N$ dominates $K_1$. But also:

Consider a shortest $u$-$C$-path $Q$ in $G+F$. As $u$ has no neighbour in $K_1$, $Q$ has length at least $2$. Let $w$ be the vertex of $C$ where $Q$ ends and let $v$ be the vertex on $Q$ preceding $w$. Using the observation preceding the claim, $v$ is not complete to $C$. We may thus assume that $Q$ was chosen such that there exists a vertex $z\in N_C(w)\setminus N_{G+F}(v)$. If $v\in K_1$, then as $u$ does not neighbour $K_1$, the path $Qz$ has length at least $4$, a contradiction to the fact that $G+F$ is $P_5$-free. Hence, $v\in N\setminus \{u\}$ and $v$ is neither complete nor anticomplete to $K_1$. If $v$ is not a neighbour of $u$ in $G+F$, then $Qz$ is an induced path in $G+F$ of length at least $4$, a contradiction. Let $x$ be a neighbour of $u$ in $K_i$. If $x$ is not a neighbour of $v$ in $G+F$, then the path $xuvwz$ is an induced $P_5$ in $G+F$, a contradiction; see Figure 1 right. Hence, $v$ has a neighbour in $K_i$, and the claim follows from Claim 9. $\mathrm{⊲}$

Assume (without loss of generality) $K_2$ is not bipartite and $G$ is $3$-colourable. From our earlier observation, if some vertex is complete to $K_1$ or to $K_2$, then $G$ is not $3$-colourable, a contradiction. As $G$ is connected, $K_2$ has a neighbour $u\in N$. Hence, $u$ is neither complete or anticomplete to $K_2$. As $u$ cannot be complete to $K_1$, by Claim 9, $u$ is anticomplete to $K_1$. Then, by Claim 10, there is a vertex in $N$ that is complete to $K_2$, a contradiction. $\mathrm{⊲}$ We can check in linear time whether $K_2,\mathrm{\dots },K_t$ are all indeed bipartite.

Let $K=K_1$ for brevity and $I=P\setminus V(K)$. Note that $G[I]$ consists only of isolated vertices and bipartite connected components. We branch on all partial 3-colourings $\psi$ that only colour every vertex of $C$. There are constantly many branches, as there are only constantly many such partial 3-colourings. We propagate the colours through $K$ by executing Algorithm 1 on $(K,\psi )$. If an error occurred, then there is no 3-colouring of $G$ that is an extension of $\psi$ by Lemma 4 (ii), and we backtrack. So we may assume that no error occurred, and for simplicity we denote the returned extension of $\psi$ by $\psi$ again.

We explicitly only propagated the colours through $K$. We now partition of $V(K)$. Let

• $\mathrm{■}$

  $K_c^i$ be the set of vertices of $K$ with colour $i$ for $i\in [3]$,

• $\mathrm{■}$

  $K_c={\bigcup }_{i\in [3]}{K}_c^i$,

• $\mathrm{■}$

  $K_u^i$ be the set of uncoloured vertices of $K$ with a neighbour of colour $i$ for $i\in [3]$,

• $\mathrm{■}$

  $K_u={\bigcup }_{i\in [3]}{K}_u^i$, and

• $\mathrm{■}$

  $K_r=V(K)\setminus (K_c\cup K_u)$ consist of the remaining vertices of $K$.

Note that $G[K_c]$ is connected, because $C$ is connected, and we assign colours to uncoloured vertices only with the Propagation Rule in Algorithm 1. Also note that the vertices of $K_u^i$ have only neighbours of colour $i\in [3]$ since they are uncoloured.

Our ultimate goal is to apply Lemma 5. So far we are not in a position to apply it, since there may be vertices (for example in $K_r$) that do not have a coloured neighbour. In the remaining proof, we distinguish two cases, depending on the length of $C$.

We show that all vertices already have a coloured neighbour.

Assume, for a contradiction, that $u\in V(G)\setminus K_c$ has no neighbour in $K_c$. Consider a shortest $u$-$C$-path $Q$ in $G+F$. Let $v$ be the vertex of $Q$ that has a neighbour in $C$. Note that $v$ is not complete to $C$; otherwise, we would have concluded that $G$ is not 3-colourable. If $v$ is in $K_c$ itself, then $Q$ has length at least 3, and there would be an induced $P_5$ in $G+F$ with vertices in $V(Q)\cup V(C)$; see Figure 2 left. Hence, $v$ is not in $K_c$. Then $v$ has at most two neighbours in $C$, and $Q$ has length at least 2, and there would be an induced $P_5$ in $G+F$ with vertices in $V(Q)\cup V(C)$, a contradiction; see Figure 2 right. $\mathrm{⊲}$

Claim 12 implies that Lemma 5 is applicable in this case. Therefore, deciding if there is a 3-colouring of $G$ that is an extension of $\psi$ is possible in polynomial time. If there is no such 3-colouring of $G$, then we backtrack.

First, note that for every vertex $v\in K_c$, we have that $v$ has two neighbours with two distinct colours in $[3]\setminus \{\psi (v)\}$, since $C$ is a clique and we assign colours to uncoloured vertices only through the Propagation Rule in Algorithm 1. We now give a more precise partition of $N$; see Figure 3. Let $M=N_G(I)$ and $L=N\setminus M$. Let

• $\mathrm{■}$

  $M_c$ and $L_c$ be the set of vertices of $M$ and $L$, respectively, that have two neighbours in $K_c$ with two distinct colours,

• $\mathrm{■}$

  $M_u^i$ and $L_u^i$ be the set of vertices of $M\setminus M_c$ and $L\setminus L_c$, respectively, with a neighbour in $K_c^i$ for $i\in [3]$,

• $\mathrm{■}$

  $M_u={\bigcup }_{i\in [3]}{M}_u^i$, $L_u={\bigcup }_{i\in [3]}{L}_u^i$,

• $\mathrm{■}$

  $M_r=M\setminus (M_c\cup M_u)$, and $L_r=L\setminus (L_c\cup L_u)$.

Let $J$ be the set of vertices of $I$ with no neighbour in $M_c$. Note that no vertex of $K_r$, $L_r$, $M_r$, and $J$ has a coloured neighbour. We now show how in the end we can apply Lemma 5.

Since $L\subseteq N$ is independent in $G$ and $G$ is connected, every vertex of $L$ has a neighbour in $K$. If, in $G$, a vertex $v\in L_r$ has only neighbours in $K_u^i$ for one $i\in [3]$, then a 3-colouring of $G-v$ that extends $\psi$ can be extended to a 3-colouring of $G$ by assigning colour $i$ to $v$. We remove any such $v$ from $G$ and continue. Now, every vertex of $L_r$ has neighbours in $K_u^i$ for at least two distinct $i\in [3]$, or has a neighbour in $K_r$. We prove two claims, one for each of the two described types of vertices in $L_r$.

Assume, for a contradiction, that $x\in K_u^i$ is a neighbour of $u$, but not a neighbour of $v$. Let $w\in K_u^j$ be a neighbour of $v$. Consider a shortest $x$-$w$-path $Q$ in $G$ with internal vertices in $K_c$. As $Qv$ is not an induced $P_5$ in $G+F$, we must have $xw\in E(G)$. Let $y$ be the neighbour of $x$ in $Q$, and let $z$ be a neighbour of $y$ that is adjacent to neither $x$ nor $w$. Note that $z$ exists since every vertex of $K_c$ has two neighbours of two distinct colours. Now, $vwxyz$ is an induced $P_5$ in $G+F$, a contradiction; see Figure 4 left. $\mathrm{⊲}$

Let $L_r^{\prime }$ be the set of vertices of $L_r$ with a neighbour in $K_r$.

If $K_r=\mathrm{\varnothing }$, then $L_r^{\prime }=\mathrm{\varnothing }$ and the statement is trivial. Hence, $K_r\ne \mathrm{\varnothing }$. As $K$ is a connected $P_5$-free graph, $K$ contains a connected dominating set $D$ that induces a $P_3$-free graph or a $C_5$ [19]. As we are in Case 2, $D$ cannot be a $C_5$. Hence, $D$ is a clique.

If $|D|\ge 4$, then $G$ contains a clique of order at least $4$, which we already excluded. If $|D|=3$, then $K$ contains a $C_3$ that dominates $K$. By the choice of $C$ and the fact that we are in Case 2, $C$ dominates $K$. Hence, our application of the Propagation Rule ensures that $K_r=\mathrm{\varnothing }$, a contradiction. If $|D|=1$ and the vertex of $D$ is in $C$, then we arrive at a contradiction as before. If $|D|=1$ and the vertex of $D$ is not in $C$, then this vertex and $C$ form a clique of order at least $4$, which we already excluded. It remains that $|D|=2$. In other words, $K$ contains a dominating edge $uv$.

We must have that $N_K(u)$ and $N_K(v)$ are disjoint; otherwise, there would be a dominating triangle in $K$, which we can exclude as before. Without loss of generality, let $N_G(u)$ contain at least two vertices of $C$. This implies $u\in K_c$. As there is no edge between $K_c$ and $K_r$ by definition of $K_r$, $v$ dominates $K_r$.

It remains to show that $v$ is complete to $L_r^{\prime }$. Suppose $y\in L_r^{\prime }\setminus N_G(v)$ exists. Let $x\in K_r$ be a neighbour of $y$. As $u$ neighbours two vertices of $C$ and $u\in K_c$, vertex $u$ is in a cycle $C^{\prime }$ of length $3$, which is contained in $K_c$ (possibly $C=C^{\prime }$). Let $z\in V(C^{\prime })\setminus \{u\}$. As $N_K(u)$ and $N_K(v)$ are disjoint, $v$ is not adjacent to $z$. Also, $z$ is not adjacent to $x$ as $x\in K_r$ and $z\in K_c$, and $y$ is not adjacent to $u$, as $y\in L_r$ and $u\in K_c$. As $zuvxy$ is not an induced $P_5$ in $G+F$, we obtain $vy\in E(G)$, a contradiction; see Figure 4 right. Hence, $v$ dominates $L_r^{\prime }$. $\mathrm{⊲}$

Claim 13 and Claim 14 together imply that:

We now describe the structure of the edges between $K$ and $M=N_G(I)$.

We first prove (i). Suppose, for the sake of contradiction, that there exists a vertex $v\in M_r$ that has a neighbour in $K$. Since $v\in M_r\subseteq M$, $v$ has a neighbour $u\in I$. By definition of $M_r$, $v$ has no neighbour in $K_c$. Let $Q$ be a shortest $v$-$C$-path in $G$ with internal vertices in $K$. The path $Q$ must contain a vertex of $K_u^i$ for some $i\in [3]$ by assumption and therefore has length at least 2. Then there is an induced $P_5$ in $G+F$ with vertices in $\{u\}\cup V(Q)\cup V(C)$, a contradiction; see Figure 5 left.

We continue with (ii). For some $i\in [3]$, let $v\in M_u^i$ such that $v$ is not complete to $K_c^i$. Since $v\in M$, $v$ has a neighbour $u\in I$. Since $v\in M_u^i$, $v$ has a neighbour in $K_c^i$. Let $x\in K_c^i$ be a non-neighbour of $v$. Let $w\in K_c^i$ be a neighbour of $v$ that is closest to $x$ in $G[K_c]$. Let $Q$ be a shortest $w$-$x$-path in $G[K_c]$, which exists since $G[K_c]$ is connected. As $w,x\in K_c^i$, they are not adjacent. Thus, $Q$ has length at least 2, and $uvQ$ contains an induced $P_5$ in $G+F$, a contradiction; see Figure 5 right. Hence, for every $i\in [3]$, $M_u^i$ is complete to $K_c^i$. $\mathrm{⊲}$

We continue with two claims describing the structure of the edges between $I$ and $M_c\cup M_u$.

Assume, for a contradiction, that the vertex $u\in I$ only has neighbours in $M_r$. Since every vertex of $M_r$ has no neighbours in $K$ by Claim 16 (i), a shortest $u$-$C$-path $Q$ in $G+F$ has length at least 3. This implies that there is an induced $P_5$ in $G+F$ with vertices in $V(Q)\cup V(C)$, a contradiction; see Figure 6 left. The claim follows. $\mathrm{⊲}$

Note that $N_G(u)\subseteq I$ by Claim 16 (i) and since $M_r\subseteq N$ is independent. Let $v,w\in N_G(u)$. Assume, for a contradiction, that the vertex $x\in M_c\cup M_u$ is a neighbour of $v$, but not a neighbour of $w$. By considering a shortest $u$-$C$-path in $G+F$ containing the vertices $v$ and $x$, we see that $ux\in F$. Let $z\in K_c$ be a vertex that is not adjacent to $x$ in $G$, which exists, or $G$ would not be $3$-colourable. Therefore, $wux$ together with a shortest $x$-$z$-path with internal vertices in $K_c$ contains an induced $P_5$ in $G+F$, a contradiction; see Figure 6 right. As $v,w\in N_G(u)$ were arbitrary, the proof is complete. $\mathrm{⊲}$

Claim 19 is an important consequence of Claims 17 and 18.

Assume, for a contradiction, that for a vertex $u\in M_r$, there exist vertices $v_i\in N_G(u)$ with ${\psi }^{\prime }(v_i)=i$ for every $i\in [3]$. Note that $v_1,v_2,v_3\in I$ by Claim 16 (i). By Claim 17 and Claim 18, there exists a vertex $w\in M_c\cup M_u$ that is adjacent to $v_1$, $v_2$, and $v_3$, a contradiction to the fact that ${\psi }^{\prime }$ is a $3$-colouring of $G-M_r$. Therefore, for every vertex $u\in M_r$, there is a colour $i\in [3]$ such that no neighbour of $u$ in $G$ has colour $i$ under ${\psi }^{\prime }$. At this point, choosing any such colour for every vertex of $M_r$ gives a 3-colouring of $G$ that is an extension of ${\psi }^{\prime }$. $\mathrm{⊲}$ Claim 19 implies that it suffices to decide if there is a 3-colouring $G-M_r$ that is an extension of $\psi$. Hence, from now on, assume that $M_r=\mathrm{\varnothing }$. Recall that $J$ is the set of vertices of $I$ with no neighbour in $M_c$. Consequently, by Claim 17, every vertex of $J$ has a neighbour in $M_u$. Claim 9 implies that every vertex of $M_c\cup M_u$ is either complete or anticomplete to each connected component of $G[I]$. It follows that, if $u\in J$, then $J$ contains all vertices of the connected component of $u$ in $G[I]$. We prove one more claim about the structure of the edges between $M_u$ and $J$.

Let $K^{\prime }$ be an arbitrary connected component of $G[J]$. Keep in mind that $K^{\prime }$ is a connected component of $G[I]$ too. Let $i,j\in [3]$ with $i\ne j$ be such that $M_u^i$ is nonempty, and $K^{\prime }$ has a neighbour $v$ in $M_u^j$. Note that such $i$ and $j$ exist by assumption and Claim 17, and $v$ is complete to $K^{\prime }$ by Claim 9. We prove that $M_u^i$ is complete to $K^{\prime }$.

Assume, for a contradiction, that $w\in M_u^i$ has no neighbour in $K^{\prime }$. Let $u$ be an arbitrary neighbour of $v$ in $K^{\prime }$. Consider a shortest $v$-$w$-path $Q$ with internal vertices in $K_c$, which exists since $G[K_c]$ is connected. As $i\ne j$, the path $Q$ has length at least 3, and, by Claim 16 (ii), the path $Q$ has length exactly 3. Since $uQ$ is not an induced $P_5$ in $G+F$, we have $vw\in F$. Let $x$ be the neighbour of $w$ in $Q$, let $k\in [3]\setminus \{i,j\}$, and let $y$ be a neighbour of $x$ in $K_c$ with colour $k$. Note that $y$ exists since every vertex of $K_c$ has two neighbours in $K_c$ with two distinct colours. Now $uvwxy$ is an induced $P_5$ in $G+F$, a contradiction; see Figure 7. So $w$ has a neighbour in $K^{\prime }$. Claim 9 implies that $w$ is complete to $K^{\prime }$. Since $w\in M_u^i$ was chosen arbitrarily, this proves that $M_u^i$ is complete to $K^{\prime }$.

A similar argument shows that for $k\in [3]\setminus \{i,j\}$, if $M_u^k$ is nonempty, then $M_u^k$ is complete to $K^{\prime }$ too. By interchanging the roles of $i$ and $j$, we see that $M_u^j$ is complete to $K^{\prime }$. Since $K^{\prime }$ was chosen arbitrarily, and since every such connected component of $G[J]$ has a neighbour in $M_u$ by Claim 17, this completes the proof. $\mathrm{⊲}$

At this point, we are in a position to decide if there is a $3$-colouring of $G$ that is an extension of $\psi$. First, Claim 15 implies that $K_r\cup L_r$ is dominated by a set $D$ of at most two vertices of $K$. We branch on the (constantly many) consistent extensions of $\psi$ into $3$-colourings that additionally colour every vertex of $D$, which we call $\psi$ again for simplicity.

Observe that every vertex of $K_r\cup L_r$ has a coloured neighbour now. As $M_r=\mathrm{\varnothing }$, we now only need to achieve the same for $J$ in order to apply Lemma 5. If $J=\mathrm{\varnothing }$, then Lemma 5 is directly applicable. Therefore, we decide in polynomial time if there is a 3-colouring of $G$ that is an extension of $\psi$. If there is no such 3-colouring, then we backtrack.

We now assume that $J\ne \mathrm{\varnothing }$. Since vertices in $J$ are not adjacent to $M_c$ by definition and $M_r=\mathrm{\varnothing }$, $M_u\ne \mathrm{\varnothing }$. If $M_u^i$ is nonempty for at least two $i\in [3]$, then we choose a vertex $v\in M_u$. We branch on the extensions ${\psi }^{\prime }$ of $\psi$ that additionally colour $v$. Observe that now every vertex of $I$ has a coloured neighbour under ${\psi }^{\prime }$ by the definition of $J$ and Claim 20. Now, Lemma 5 is applicable. Therefore, we decide in polynomial time if there is a 3-colouring of $G$ that is an extension of ${\psi }^{\prime }$. If there is no such 3-colouring, then we backtrack.

It remains the case that there is exactly one $i\in [3]$ such that $M_u^i$ is nonempty. Every vertex in $J$ has neighbours only in $J\cup M_u^i$. In particular, for each connected component $K^{\prime }$ of $G[J]$, which is a connected component of $G[I]$, the colour $i$ may be used without creating conflicts outside of $K^{\prime }$. Recall that $K^{\prime }$ is bipartite by Claim 11. Hence, we wish to extend $\psi$ by, for each connected component $K^{\prime }$ of $G[J]$, colouring one of its partite set by colour $i$. However, we cannot immediately decide which partite set, and make a small detour.

Let $K^{\prime }$ be a connected component of $G[J]$ that contains an edge. Let $u$ be a neighbour of $K^{\prime }$ in $M_u^i$. Since $u\in M_u^i$, it is adjacent to $K$, and thus neither complete nor anticomplete to $K$. Hence, $u$ is complete to $K^{\prime }$ by Claim 9. Thus, $N_G(K^{\prime })$ is complete to $K^{\prime }$. Therefore, all vertices of $N_G(K^{\prime })$ must receive the same colour in any $3$-colouring of $G$ that extends $\psi$. We ensure this first, for each such connected component $K^{\prime }$, and then extend the colouring to $J$.

We apply the formula $ℱ$ of Lemma 5 to $G-J$, adapted as follows. For every connected component $K^{\prime }$ in $G[J]$ that contains an edge, and for every two distinct vertices $u,v\in N_G(K^{\prime })$, we add the clauses $({\overline{x}}_u^k\vee x_v^k)\wedge (x_u^k\vee {\overline{x}}_v^k)$ to $ℱ$ for every $k\in [3]\setminus \{i\}$. These clauses ensure that two such vertices $u$ and $v$ receive the same colour. (Alternatively we could identify these vertices. At this point it does not matter that this does not preserve probe $P_5$-freeness.) After that, we resolve the satisfiability of the 2-SAT formula $ℱ$ in polynomial time [3]. If $ℱ$ is not satisfiable, then there is no 3-colouring of $G$ that is an extension of $\psi$, and we backtrack. Otherwise, let ${\psi }^{\prime }$ be a 3-colouring of $G-J$ obtained from a satisfying assignment of $ℱ$. We can extend ${\psi }^{\prime }$ to a $3$-colouring of $G$ by assigning colour $i$ to isolated vertices in $G[J]$, and by assigning the remaining two colours to the nontrivial bipartite connected components of $G[J]$, which is possible due to the extra clauses we added to $ℱ$. This completes the proof of Theorem 8. $◀$

We reduce an instance $(3,G,\psi ,\{v_1,v_2,v_3\})$ of 1-Precolouring Extension, where $G$ is a bipartite graph with bipartition $A$ and $B$, and the precoloured vertices $v_1,v_2,v_3$ belong to $A$ without loss of generality, to an instance of $3$-Colouring. As mentioned, this variant of 1-Precolouring Extension is still $\mathrm{𝖭𝖯}$-complete [7]. The bipartition of $G$ can be computed in polynomial time. Let $G^{\prime }$ be the graph from [18], which is obtained in polynomial-time from $G$ by turning $\{v_1,v_2,v_3\}$ into a clique. The graph $G^{\prime }$ is probe $(P_6,2P_3,3P_2)$-free, which is witnessed by the fact that the graph obtained from $G^{\prime }$ by turning the independent set $B$ into a clique is $(P_6,2P_3,3P_2)$-free. It is easy to see that $(3,G,\psi ,\{v_1,v_2,v_3\})$ is a yes-instance of 1-Precolouring Extension if and only if $(G^{\prime },A,B)$ is a yes-instance of $3$-Colouring. This proves that $3$-Colouring is $\mathrm{𝖭𝖯}$-hard on partitioned probe $(P_6,2P_3,3P_2)$-free graphs. $◀$