# Colouring $(P_{r}+P_{s})$-Free Graphs††thanks:  T. Masařík, J. Novotná and
V. Slívová were supported by the project GAUK 1277018 and the grant
SVV–2017–260452. T. Klimošová was supported by the Center of Excellence – ITI,
project P202/12/G061 of GA ČR, by the Center for Foundations of Modern
Computer Science (Charles Univ. project UNCE/SCI/004), and by the project GAUK
1277018. T. Masařík was also partly supported by the Center of Excellence –
ITI, project P202/12/G061 of GA ČR. V. Slívová was partly supported by the
project 17-09142S of GA ČR and Charles University project PRIMUS/17/SCI/9. D.
Paulusma was supported by the Leverhulme Trust (RPG-2016-258).

Tereza Klimošová  Department of Applied Mathematics, Faculty of Mathematics
and Physics,
Charles University, Prague, Czech Republic  Josef Malík  Czech Technical
University in Prague, Czech Republic  Tomáš Masařík  Department of Applied
Mathematics, Faculty of Mathematics and Physics,
Charles University, Prague, Czech Republic
Jana Novotná  Department of Applied Mathematics, Faculty of Mathematics and
Physics,
Charles University, Prague, Czech Republic  Daniël Paulusma  Department of
Computer Science, Durham University, Durham, UK  Veronika Slívová  Computer
Science Institute, Faculty of Mathematics and Physics,
Charles University, Prague, Czech Republic

###### Abstract

The $k$-Colouring problem is to decide if the vertices of a graph can be
coloured with at most $k$ colours for a fixed integer $k$ such that no two
adjacent vertices are coloured alike. If each vertex $u$ must be assigned a
colour from a prescribed list $L(u)\subseteq\\{1,\ldots,k\\}$, then we obtain
the List $k$-Colouring problem. A graph $G$ is $H$-free if $G$ does not
contain $H$ as an induced subgraph. We continue an extensive study into the
complexity of these two problems for $H$-free graphs. The graph $P_{r}+P_{s}$
is the disjoint union of the $r$-vertex path $P_{r}$ and the $s$-vertex path
$P_{s}$. We prove that List $3$-Colouring is polynomial-time solvable for
$(P_{2}+P_{5})$-free graphs and for $(P_{3}+P_{4})$-free graphs. Combining our
results with known results yields complete complexity classifications of
$3$-Colouring and List $3$-Colouring on $H$-free graphs for all graphs $H$ up
to seven vertices. We also prove that 5-Colouring is $\mathsf{NP}$-complete
for $(P_{3}+P_{5})$-free graphs.

Keywords:  Vertex colouring, $H$-free graph, linear forest.

##  1 Introduction

Graph colouring is a popular concept in Computer Science and Mathematics due
to a wide range of practical and theoretical applications, as evidenced by
numerous surveys and books on graph colouring and many of its variants (see,
for example, [1, 6, 15, 23, 25, 29, 31, 34]). Formally, a colouring of a graph
$G=(V,E)$ is a mapping $c:V\rightarrow\\{1,2,\ldots\\}$ that assigns each
vertex $u\in V$ a colour $c(u)$ in such a way that $c(u)\neq c(v)$ whenever
$uv\in E$. If $1\leq c(u)\leq k$, then $c$ is also called a $k$-colouring of
$G$ and $G$ is said to be $k$-colourable. The Colouring problem is to decide
if a given graph $G$ has a $k$-colouring for some given integer $k$.

It is well known that Colouring is $\mathsf{NP}$-complete even if $k=3$ [28].
To pinpoint the reason behind the computational hardness of Colouring one may
impose restrictions on the input. This led to an extensive study of Colouring
for special graph classes, particularly hereditary graph classes. A graph
class is hereditary if it is closed under vertex deletion. As this is a
natural property, hereditary graph classes capture a very large collection of
well-studied graph classes. A classical result in this area is due to
Grötschel, Lovász, and Schrijver [18], who proved that Colouring is
polynomial-time solvable for perfect graphs.

It is readily seen that a graph class ${\cal G}$ is hereditary if and only if
${\cal G}$ can be characterized by a unique set ${\cal H}_{\cal G}$ of minimal
forbidden induced subgraphs. A graph $G\in{\cal G}$ is $H$-free if ${\cal
H_{\cal G}}$ only contains one graph $H$, that is, $G$ has no induced subgraph
isomorphic to $H$. Král’, Kratochvíl, Tuza, and Woeginger [24] started a
systematic study into the complexity of Colouring on ${\cal H}$-free graphs
for sets ${\cal H}$ of size at most 2. They showed polynomial-time solvability
if $H$ is an induced subgraph of $P_{4}$ or $P_{1}+P_{3}$ and
$\mathsf{NP}$-completeness for all other graphs $H$. The classification for
the case where ${\cal H}$ has size 2 is far from finished; see the summary in
[15] or an updated partial overview in [12] for further details. Instead of
considering sets ${\cal H}$ of size 2, we consider $H$-free graphs and follow
another well-studied direction, in which the number of colours $k$ is fixed,
that is, $k$ no longer belongs to the input. This leads to the following
decision problem:

$k$-Colouring
Instance: a graph $G$. Question: does there exist a $k$-colouring of $G$?

To obtain more general results, we also consider a generalization of the
$k$-Colouring problem. A $k$-list assignment of $G$ is a function $L$ with
domain $V$ such that the list of admissible colours $L(u)$ of each $u\in V$ is
a subset of $\\{1,2,\dots,k\\}$. A colouring $c$ respects ${L}$ if $c(u)\in
L(u)$ for every $u\in V.$ If $k$ is fixed, then we obtain the following
decision problem:

List $k$-Colouring
Instance: a graph $G$ and a $k$-list assignment $L$. Question: does there
exist a colouring of $G$ that respects $L$?

Note that $k$-Colouring is polynomial-time solvable if List $k$-Colouring is
so, and that List $k$-Colouring is $\mathsf{NP}$-complete if $k$-Colouring is
so. For every $k\geq 3$, $k$-Colouring on $H$-free graphs is
$\mathsf{NP}$-complete if $H$ contains a cycle [14] or an induced claw [21,
27]. Hence, it remains to consider the case where $H$ is a linear forest (a
disjoint union of paths). The situation is far from settled yet, although many
partial results are known [3, 4, 5, 7, 8, 9, 10, 11, 16, 20, 22, 26, 30, 32,
35]. Particularly, the case where $H$ is the $t$-vertex path $P_{t}$ has been
well studied. The cases $k=4$, $t=7$ and $k=5$, $t=6$ are
$\mathsf{NP}$-complete [22]. For $k\geq 1$, $t=5$ [20] and $k=3$, $t=7$ [3],
even List $k$-Colouring on $P_{t}$-free graphs is polynomial-time solvable
(see also [15]). For a fixed integer $k$, the $k$-Precolouring Extension
problem is to test whether a given $k$-colouring defined on an induced
subgraph of a graph $G$ can be extended to a $k$-colouring of $G$. Recently it
was shown in [8, 9] that 4-Precolouring Extension, and therefore 4-Colouring,
is polynomial-time solvable for $P_{6}$-free graphs. In contrast, the more
general problem List $4$-Colouring is $\mathsf{NP}$-complete for $P_{6}$-free
graphs [16]. See Table 1 for a summary of all these results.

|  $k$-Colouring | $k$-Precolouring Extension | List $k$-Colouring
---|---|---|---
$\;\;t\;\;$ | $k=3$ | $k=4$ | $k=5$ | $k\geq 6$ | $k=3$ | $k=4$ | $k=5$ | $k\geq 6$ | $k=3$ | $k=4$ | $k=5$ | $k\geq 6$
$t\leq 5$ | P | P | P | P | P | P | P | P | P | P | P | P
$t=6$ | P | P | NP-c | NP-c | P | P | NP-c | NP-c | P | NP-c | NP-c | NP-c
$t=7$ | P | NP-c | NP-c | NP-c | P | NP-c | NP-c | NP-c | P | NP-c | NP-c | NP-c
$t\geq 8$ | ? | NP-c | NP-c | NP-c | ? | NP-c | NP-c | NP-c | ? | NP-c | NP-c | NP-c

Table 1: Summary for $P_{t}$-free graphs.

From Table 1 we see that only the cases $k=3$, $t\geq 8$ are still open,
although some partial results are known for $k$-Colouring for the case $k=3$,
$t=8$ [10]. The situation when $H$ is a disconnected linear forest $\bigcup
P_{i}$ is less clear. It is known that for every $s\geq 1$, List 3-Colouring
is polynomial-time solvable for $sP_{3}$-free graphs [5, 15]. For every graph
$H$, List $3$-Colouring is polynomial-time solvable for $(H+P_{1})$-free
graphs if it is polynomially solvable for $H$-free graphs [5, 15]. If
$H=rP_{1}+P_{5}$ $(r\geq 0)$ a stronger result is known.

######  Theorem 1 ([11]).

For all $k\geq 1,r\geq 0$, List $k$-Colouring is polynomial-time solvable on
$(rP_{1}+P_{5})$-free graphs.

Theorem 1 cannot be extended to larger linear forests $H$, as List
$4$-Colouring is $\mathsf{NP}$-complete for $P_{6}$-free graphs [16] and List
$5$-Colouring is $\mathsf{NP}$-complete for $(P_{2}+P_{4})$-free graphs [11].
It is not clear if such an extension still exists for $k$-Colouring. It is
known that $5$-Colouring is $\mathsf{NP}$-complete for $P_{6}$-free graphs
[22], but the following problem is still open:

Do there exist integers $k\geq 3$ and $2\leq r\leq 5$ such that $k$-Colouring
is $\mathsf{NP}$-complete for $(P_{r}+P_{5})$-free graphs?

Another way of making progress is to complete a classification by bounding the
size of $H$. It follows from the above results and the ones in Table 1 that
for a graph $H$ with $|V(H)|\leq 6$, $3$-Colouring and List $3$-Colouring (and
consequently, $3$-Precolouring Extension) are polynomial-time solvable on
$H$-free graphs if $H$ is a linear forest, and $\mathsf{NP}$-complete
otherwise (see also [15]). There are two open cases [15] that must be solved
in order to obtain the same statement for graphs $H$ with $|V(H)|\leq 7$.
These cases are

  * $\bullet$

$H=P_{2}+P_{5}$

  * $\bullet$

$H=P_{3}+P_{4}$.

### Our Results

We consider the above research questions for disconnected forests $H$. In
Section 2 we address the two missing cases listed above by proving the
following theorem.

######  Theorem 2.

List $3$-Colouring is polynomial-time solvable for $(P_{2}+P_{5})$-free graphs
and for $(P_{3}+P_{4})$-free graphs.

We prove Theorem 2 as follows. If the graph $G$ of an instance $(G,L)$ of List
$3$-Colouring is $P_{7}$-free, then we can use the aforementioned result of
Bonomo et al. [3]. Hence we may assume that $G$ contains an induced $P_{7}$.
We consider every possibility of colouring the vertices of this $P_{7}$ and
try to reduce each resulting instance to a polynomial number of smaller
instances of $2$-Satisfiability. As the latter problem can be solved in
polynomial time, the total running time of the algorithm will be polynomial.
The crucial proof ingredient is that we partition the set of vertices of $G$
that do not belong to the $P_{7}$ into subsets of vertices that are of the
same distance to the $P_{7}$. This leads to several “layers” of $G$. We
analyse how the vertices of each layer are connected to each other and to
vertices of adjacent layers so as to use this information in the design of our
algorithm.

Combining Theorem 2 with the known results yields the following complexity
classifications for graphs $H$ up to seven vertices; see Section 3 for its
proof.

######  Corollary 1.

Let $H$ be a graph with $|V(H)|\leq 7$. If $H$ is a linear forest, then List
$3$-Colouring is polynomial-time solvable for $H$-free graphs; otherwise
already $3$-Colouring is $\mathsf{NP}$-complete for $H$-free graphs.

In Section 4 we complement Theorem 2 by proving the following result.

######  Theorem 3.

$5$-Colouring is $\mathsf{NP}$-complete for $(P_{3}+P_{5})$-free graphs.

Theorems 2 and 3 reduce the first research question to the question whether
there exists an integer $k\geq 4$ such that $k$-Colouring is
$\mathsf{NP}$-complete for $(P_{2}+P_{5})$-free graphs.

### Preliminaries

Let $G=(V,E)$ be a graph. For a vertex $v\in V$, we denote its _neighbourhood_
by $N(v)=\\{u\;|\;uv\in E\\}$, its closed neighbourhood by
$N[v]=N(v)\cup\\{v\\}$ and its degree by $\deg(v)=|N(v)|$. For a set
$S\subseteq V$, we write $N(S)=\bigcup_{v\in S}N(v)\setminus S$ and
$N[S]=N(S)\cup S$, and we let $G[S]=(S,\\{uv\;|\;u,v\in S\\})$ be the subgraph
of $G$ induced by $S$. The contraction of an edge $e=uv$ removes $u$ and $v$
from $G$ and introduces a new vertex which is made adjacent to every vertex in
$N(u)\cup N(v)$. The identification of a set $S\subseteq V$ by a vertex $w$
removes all vertices of $S$ from $G$, introduces $w$ as a new vertex and makes
$w$ adjacent to every vertex in $N(S)$. The length of a path is its number of
edges. The distance $\operatorname{dist}_{G}(u,v)$ between two vertices $u$
and $v$ is the length of a shortest path between them in $G$. The distance
$\operatorname{dist}_{G}(u,S)$ between a vertex $u\in V$ and a set $S\subseteq
V\setminus\\{v\\}$ is defined as $\min\\{\operatorname{dist}(u,v)\;|\;v\in
S\\}$.

For two graphs $G$ and $H$, we use $G+H$ to denote the disjoint union of $G$
and $H$, and we write $rG$ to denote the disjoint union of $r$ copies of $G$.
Let $(G,L)$ be an instance of List 3-Colouring. For $S\subseteq V(G)$, we
write $L(S)=\bigcup_{u\in S}L(u)$. We let $P_{n}$ and $K_{n}$ denote the path
and complete graph on $n$ vertices, respectively. The diamond is the graph
obtained from $K_{4}$ after removing an edge.

We say that an instance $(G^{\prime},L^{\prime})$ is smaller than some other
instance $(G,L)$ of List 3-Colouring if either $G^{\prime}$ is an induced
subgraph of $G$ with $|V(G^{\prime})|<|V(G)|$; or $G^{\prime}=G$ and
$L^{\prime}(u)\subseteq L(u)$ for each $u\in V(G)$, such that there exists at
least one vertex $u^{*}$ with $L^{\prime}(u^{*})\subset L(u^{*})$.

##  2 The Two Polynomial-Time Results

In this section we show that List $3$-Colouring problem is polynomial-time
solvable for $(P_{2}+P_{5})$-free graphs and for $(P_{3}+P_{4})$-free graphs.
As arguments for these two graph classes are overlapping, we prove both cases
simultaneously. Our proof uses the following two results.

######  Theorem 4 ([3]).

List $3$-Colouring is polynomial-time solvable for $P_{7}$-free graphs.

If we cannot apply Theorem 4, our strategy is to reduce, in polynomial time,
an instance $(G,L)$ of List 3-Colouring to a polynomial number of smaller
instances of 2-List Colouring. We use the following well-known result due to
Edwards.

######  Theorem 5 ([13]).

The $2$-List Colouring problem is linear-time solvable.

We are now ready to prove our main result , namely that List $3$-Colouring is
polynomial-time solvable for $(P_{2}+P_{5})$-free graphs and for
$(P_{3}+P_{4})$-free graphs. As arguments for these two graph classes are
overlapping, we prove both cases simultaneously. We start with an outline
followed by a formal proof.

Outline of the proof of Theorem 2. Our goal is to reduce, in polynomial time,
a given instance $(G,L)$ of List 3-Colouring, where $G$ is
$(P_{2}+P_{5})$-free or $(P_{3}+P_{4})$-free, to a polynomial number of
smaller instances of 2-List-Colouring in such a way that $(G,L)$ is a yes-
instance if and only if at least one of the new instances is a yes-instance.
As for each of the smaller instances we can apply Theorem 5, the total running
time of our algorithm will be polynomial.

If $G$ is $P_{7}$-free, then we do not have to do the above and may apply
Theorem 4 instead. Hence, we assume that $G$ contains an induced $P_{7}$. We
put the vertices of the $P_{7}$ in a set $N_{0}$ and define sets $N_{i}$
$(i\geq 1$) of vertices of the same distance $i$ from $N_{0}$; we say that the
sets $N_{i}$ are the layers of $G$. We then analyse the structure of these
layers using the fact that $G$ is $(P_{2}+P_{5})$-free or
$(P_{3}+P_{4})$-free. The first phase of our algorithm is about preprocessing
$(G,L)$ after colouring the seven vertices of $N_{0}$ and applying a number of
propagation rules. We consider every possible colouring of the vertices of
$N_{0}$. In each branch we may have to deal with vertices $u$ that still have
a list $L(u)$ of size 3. We call such vertices active and prove that they all
belong to $N_{2}$. We then enter the second phase of our algorithm. In this
phase we show, via some further branching, that $N_{1}$-neighbours of active
vertices either all have a list from $\\{\\{h,i\\},\\{h,j\\}\\}$, where
$\\{h,i,j\\}=\\{1,2,3\\}$, or they all have the same list $\\{h,i\\}$. In the
third phase we reduce, again via some branching, to the situation where only
the latter option applies: $N_{1}$-neighbours of active vertices all have the
same list. Then in the fourth and final phase of our algorithm we know so much
structure of the instance that we can reduce to a polynomial number of smaller
instances of 2-List-Colouring via a new propagation rule identifying common
neighbourhoods of two vertices by a single vertex.

Theorem 2 (restated). List $3$-Colouring is polynomial-time solvable for
$(P_{2}+P_{5})$-free graphs and for $(P_{3}+P_{4})$-free graphs.

###### Proof.

Let $(G,L)$ be an instance of List 3-Colouring, where $G=(V,E)$ is an $H$-free
graph for $H\in\\{P_{2}+P_{5},P_{3}+P_{4}\\}$. Note that $G$ is
$(P_{3}+P_{5})$-free. Since the problem can be solved component-wise, we may
assume that $G$ is connected. If $G$ contains a $K_{4}$, then $G$ is not
3-colourable, and thus $(G,L)$ is a no-instance. As we can decide if $G$
contains a $K_{4}$ in $O(n^{4})$ time by brute force, we assume that from now
on $G$ is $K_{4}$-free. By brute force we either deduce in $O(n^{7})$ time
that $G$ is $P_{7}$-free or we find an induced $P_{7}$ on vertices
$v_{1},\ldots,v_{7}$ in that order. In the first case we use Theorem 4. It
remains to deal with the second case.

Definition (Layers). Let $N_{0}=\\{v_{1},\ldots,v_{7}\\}.$ For $i\geq 1$, we
define $N_{i}=\\{u\>|\;\operatorname{dist}(u,N_{0})=i\\}$. We call the sets
$N_{i}$ $(i\geq 0)$ the layers of $G$.

In the remainder, we consider $N_{0}$ to be a fixed set of vertices. That is,
we will update $(G,L)$ by applying a number of propagation rules and doing
some (polynomial) branching, but we will never delete the vertices of $N_{0}$.
This will enable us to exploit the $H$-freeness of $G$.

We show the following two claims about layers.

######  Claim 1.

$V=N_{0}\cup N_{1}\cup N_{2}\cup N_{3}$.

Proof of Claim 1. Suppose $N_{i}\neq\emptyset$ for some $i\geq 4$. As $G$ is
connected, we may assume that $i=4$. Let $u_{4}\in N_{4}$. By definition,
there exists two vertices $u_{3}\in N_{3}$ and $u_{2}\in N_{2}$ such that
$u_{2}$ is adjacent to $u_{3}$ and $u_{3}$ is adjacent to $u_{4}$. Then $G$
has an induced $P_{3}+P_{5}$ on vertices
$u_{2},u_{3},u_{4},v_{1},v_{2},v_{3},v_{4},v_{5}$, a contradiction. $\diamond$

######  Claim 2.

$G[N_{2}\cup N_{3}]$ is the disjoint union of complete graphs of size at most
$3$, each containing at least one vertex of $N_{2}$ (and thus at most two
vertices of $N_{3}$).

Proof of Claim 2. First assume that $G[N_{2}\cup N_{3}]$ has a connected
component $D$ that is not a clique. Then $D$ contains an induced $P_{3}$,
which together with the subgraph $G[\\{v_{1},\ldots,v_{5}\\}$] forms an
induced $P_{3}+P_{5}$, a contradiction. Then the claim follows after recalling
that $G$ is $K_{4}$-free and connected. $\diamond$

We will now introduce a number of propagation rules, which run in polynomial
time. We are going to apply these rules on $G$ exhaustively, that is, until
none of the rules can be applied anymore. Note that during this process some
vertices $G$ may be deleted (due to Rules 4 and 10), but as mentioned we will
ensure that we keep the vertices of $N_{0}$, while we may update the other
sets $N_{i}$ $(i\geq 1)$. We say that a propagation rule is safe if the new
instance is a yes-instance of List 3-Colouring if and only if the original
instance is so.

  1. Rule 1.

(no empty lists) If $L(u)=\emptyset$ for some $u\in V$, then return no.

  2. Rule 2.

(no lists of size 3) If $|L(u)|\leq 2$ for every $u\in V$, then apply Theorem
5.

  3. Rule 3.

(connected graph) If $G$ is disconnected, then solve List 3-Colouring on each
instance $(D,L_{D})$, where $D$ is a connected component of $G$ that does not
contain $N_{0}$ and $L_{D}$ is the restriction of $L$ to $D$. If $D$ has no
colouring respecting $L_{D}$, then return no; otherwise remove the vertices of
$D$ from $G$.

  4. Rule 4.

(no coloured vertices) If $u\notin N_{0}$, $|L(u)|=1$ and $L(u)\cap
L(v)=\emptyset$ for all $v\in N(u)$, then remove $u$ from $G$.

  5. Rule 5.

(single colour propagation) If $u$ and $v$ are adjacent, $|L(u)|=1$, and
$L(u)\subseteq L(v)$, then set $L(v):=L(v)\setminus L(u)$.

  6. Rule 6.

(diamond colour propagation) If $u$ and $v$ are adjacent and share two common
neighbours $x$ and $y$ with $L(x)\neq L(y)$, then set $L(x):=L(x)\cap L(y)$
and $L(y):=L(x)\cap L(y)$.

  7. Rule 7.

(twin colour propagation) If $u$ and $v$ are non-adjacent, $N(u)\subseteq
N(v)$, and $L(v)\subset L(u)$, then set $L(u):=L(v)$.

  8. Rule 8.

(triangle colour propagation) If $u,v,w$ form a triangle, $|L(u)\cup L(v)|=2$
and $|L(w)|\geq 2$, then set $L(w)\operatorname{:=}L(w)\setminus(L(u)\cup
L(v))$, so $|L(w)|\leq 1$.

  9. Rule 9.

(no free colours) If $|L(u)\setminus L(N(u))|\geq 1$ and $|L(u)|\geq 2$ for
some $u\in V$, then set $L(u):=\\{c\\}$ for some $c\in L(u)\setminus L(N(u))$.

  10. Rule 10.

(no small degrees) If $|L(u)|>|\deg(u)|$ for some $u\in V\setminus N_{0}$,
then remove $u$ from $G$.

As mentioned, our algorithm will branch at several stages to create a number
of new but smaller instances, such that the original instance is a yes-
instance if and only if at least one of the new instances is a yes-instance.
Unless we explicitly state otherwise, we implicitly assume that Rules 1–10 are
applied exhaustively immediately after we branch (the reason why we may do
this is shown in Claim 3). If we apply Rule 1 or 2 on a new instance, then a
no-answer means that we will discard the branch. So our algorithm will only
return a no-answer for the original instance $(G,L)$ if we discarded all
branches. On the other hand, if we can apply Rule 2 on some new instance and
obtain a yes-answer, then we can extend the obtained colouring to a colouring
of $G$ that respects $L$, simply by restoring all the already coloured
vertices that were removed from the graph due to the rules. We will now state
Claim 3.

######  Claim 3.

Rules 1–10 are safe and their exhaustive application takes polynomial time.
Moreover, if we have not obtained a yes- or no-answer, then afterwards $G$ is
a connected $(H,K_{4})$-free graph, such that $V=N_{0}\cup N_{1}\cup N_{2}\cup
N_{3}$ and $2\leq|L(u)|\leq 3$ for every $u\in V\setminus N_{0}$.

Proof of Claim 3. It is readily seen that Rules 1–5 are safe. For Rule 6, this
follows from the fact that any 3-colouring assigns $x$ and $y$ the same
colour. For Rule 7, this follows from the fact that $u$ can always be
recoloured with the same colour as $v$. For Rule 8, this follows from the fact
that the colours from $L(u)\cup L(v)$ must be used on $u$ and $v$. For Rule 9,
this follows from the fact that no colour from $L(u)\setminus L(N(u))$ will be
assigned to a vertex in $N(u)$. For Rule 10, this follows from the fact that
we always have a colour available for $u$.

It is readily seen that applying Rules 1, 2 and 4–10 take polynomial time.
Applying Rule 3 takes polynomial time, as each connected component of $G$ that
does not contain $N_{0}$ is a complete graph on at most three vertices due to
the $(H,K_{4})$-freeness of $G$ (recall that $H=P_{2}+P_{3}$ or
$H=P_{3}+P_{4}$). Each application of a rule either results in a no-answer, a
yes-answer, reduces the list size of at least one vertex, or reduces $G$ by at
least one vertex. Thus exhaustive application of the rules takes polynomial
time.

Suppose exhaustive application does not yield a no-answer or a yes-answer. By
Rule 3, $G$ is connected. As no vertex of $N_{0}$ was removed, $G$ contains
$N_{0}$. Hence, we can define $V=N_{0}\cup N_{1}\cup N_{2}\cup N_{3}$ by Claim
1. By Rules 4 and 5, we find that $2\leq|L(u)|\leq 3$ for every $u\in
V\setminus N_{0}$. It is readily seen that Rules 1–10 preserve
$(H,K_{4})$-freeness of $G$. $\diamond$

### Phase 1. Preprocessing $\mathbf{(G,L)}$

In Phase 1 we will preprocess $(G,L)$ using the above propagation rules. To
start off the preprocessing we will branch via colouring the vertices of
$N_{0}$ in every possible way. To start off the preprocessing we will branch
via colouring the vertices of $N_{0}$ in every possible way. By colouring a
vertex $u$, we mean reducing the list of permissible colours to size exactly
one. (When $L(u)=\\{c\\}$, we consider vertex coloured by colour $c$.) Thus,
when we colour some vertex $u$, we always give $u$ a colour from its list
$L(u)$, moreover, when we colour more than one vertex we will always assign
distinct colours to adjacent vertices.

Branching I ($O(1)$ branches)
We now consider all possible combinations of colours that can be assigned to
the vertices in $N_{0}$. That is, we branch into at most $3^{7}$ cases, in
which $v_{1},\ldots,v_{7}$ each received a colour from their list. We note
that each branch leads to a smaller instance and that $(G,L)$ is a yes-
instance if and only if at least one of the new instances is a yes-instance.
Hence, if we applied Rule 1 in some branch, then we discard the branch. If we
applied Rule 2 and obtained a no-answer, then we discard the branch as well.
If we obtained a yes-answer, then we are done. Otherwise we continue by
considering each remaining branch separately. For each remaining branch, we
denote the resulting smaller instance by $(G,L)$ again.

We will now introduce a new rule, namely Rule 11. We apply Rule 11 together
with the other rules. That is, we now apply Rules 1–11 exhaustively. However,
each time we apply Rule 11 we first ensure that Rules 1–10 have been applied
exhaustively.

  1. Rule 11

($\mathbf{N_{3}}$-reduction) If $u$ and $v$ are in $N_{3}$ and are adjacent,
then remove $u$ and $v$ from $G$.

######  Claim 4.

Rule 11, applied after exhaustive application of Rules 1–10, is safe and takes
polynomial time. Moreover, afterwards $G$ is a connected $(H,K_{4})$-free
graph, such that $V=N_{0}\cup N_{1}\cup N_{2}\cup N_{3}$ and $2\leq|L(u)|\leq
3$ for every $u\in V\setminus N_{0}$.

Proof of Claim 4. Assume that we applied Rules 1–10 exhaustively and that
$N_{3}$ contains two adjacent vertices $u$ and $v$. By Claim 2, we find that
$u$ and $v$ have a common neighbour $w\in N_{2}$ and no other neighbours. By
Rules 4, 5 and 10, we then find that $|L(u)|=|L(v)|=2$. First suppose that
$L(u)=L(v)$, say $L(u)=L(v)=\\{1,2\\}$. Then, by Rule 8, we find that
$L(w)=\\{3\\}$, contradicting Rule 4. Hence $L(u)\neq L(v)$, say
$L(u)=\\{1,2\\}$ and $L(v)=\\{1,3\\}$. By Rule 8, we find that
$L(w)=\\{2,3\\}$ or $L(w)=\\{1,2,3\\}$. If $w$ gets colour 1, we can give $u$
colour 2 and $v$ colour 3. If $w$ gets colour 2, we can give $u$ colour 1 and
$v$ colour 3. Finally, if $w$ gets colour 3, then we can give $u$ colour 2 and
$v$ colour 1. Hence we may set $V:=V\setminus\\{u_{1},u_{2}\\}$. This does not
destroy the connectivity or $(H,K_{4})$-freeness of $G$. $\diamond$

We now show the following claim.

######  Claim 5.

The set $N_{3}$ is independent, and moreover, each vertex $u\in N_{3}$ has
$|L(u)|=2$ and exactly two neighbours in $N_{2}$.

Proof of Claim 5. By Rule 11, we find that $N_{3}$ is independent. As every
vertex of $N_{3}$ has at most two neighbours in $N_{2}$ due to Claim 2, the
claim follows from Rules 4, 5, 10 and the fact that $N_{3}$ is independent.
$\diamond$

[mode=image,scale=0.7]layers_valid

Figure 1: All possible connected components in $G[N_{2}\cup N_{3}]$.

The following claim follows immediately from Claims 2 and 5 and gives a
complete description of the second and third layer, see also Figure 1.

######  Claim 6.

Every connected component $D$ of $G[N_{2}\cup N_{3}]$ is a complete graph with
either $|D|\leq 2$ and $D\subseteq N_{2}$, or $|D|=3$ and $|D\cap N_{3}|\leq
1$.

The following claim describes the location of the vertices with list of size 3
in $G$.

######  Claim 7.

For every $u\in V$, if $|L(u)|=3$, then $u\in N_{2}$.

Proof of Claim 7. As the vertices in $N_{0}$ have lists of size 1, the
vertices in $N_{1}$ have lists of size 2. By Claim 5, the same holds for
vertices in $N_{3}$. $\diamond$

In the remainder of the proof we will show how to branch in order to reduce
the lists of the vertices $u\in N_{2}$ with $|L(u)|=3$ by at least one colour.
We formalize this approach in the following definition.

Definition (Active vertices). A vertex $u\in N_{2}$ and its neighbours in
$N_{1}$ are called _active_ if $|L(u)|=3$. Let $A$ be the set of all active
vertices. Let $A_{1}=A\cap N_{1}$ and $A_{2}=A\cap N_{2}$. We _deactivate_ a
vertex $u\in A_{2}$ if we reduce the list $L(u)$ by at least one colour. We
_deactivate_ a vertex $w\in A_{1}$ by deactivating all its neighbours in
$A_{2}$.

Note that every vertex $w\in A_{1}$ has $|L(w)|=2$ by Rule 5 applied on the
vertices of $N_{0}$. Hence, if we reduce $L(w)$ by one colour, all neighbours
of $w$ in $A_{2}$ become deactivated by Rule 5, and $w$ is removed by Rule 4.

For $1\leq i<j\leq 7$, we let $A(i,j)\subseteq A_{1}$ be the set of active
neighbours of $v_{i}$ that are not adjacent to $v_{j}$ and similarly, we let
$A(j,i)\subseteq A_{1}$ be the set of active neighbours of $v_{j}$ that are
not adjacent to $v_{i}$.

### Phase 2. Reduce the number of distinct sets $\mathbf{A(i,j)}$

We will now branch into $O(n^{45})$ smaller instances such that $(G,L)$ is a
yes-instance of List 3-Colouring if and only if at least one of these new
instances is a yes-instance. Each new instance will have the following
property:

(P)

for $1\leq i\leq j\leq 7$ with $j-i\geq 2$, either $A(i,j)=\emptyset$ or
$A(j,i)=\emptyset$.

Branching II
($O\bigl{(}n^{\bigl{(}3\cdot\left(\binom{7}{2}-6\right)\bigr{)}}\bigr{)}=O(n^{45})$
branches)
Consider two vertices $v_{i}$ and $v_{j}$ with $1\leq i\leq j\leq 7$ and
$j-i\geq 2$. Assume without loss of generality that $v_{i}$ is coloured 3 and
that $v_{j}$ is coloured either 1 or 3. Hence, every $w\in A(i,j)$ has
$L(w)=\\{1,2\\}$, whereas every $w\in A(j,i)$ has $L(w)=\\{2,q\\}$ for
$q\in\\{1,3\\}$. We branch as follows. We consider all possibilities where at
most one vertex of $A(i,j)$ receives colour 2 (and all other vertices of
$A(i,j)$ receive colour 1) and all possibilities where we choose two vertices
from $A(i,j)$ to receive colour 2. This leads to $O(n)+O(n^{2})=O(n^{2})$
branches. In the branches where at most one vertex of $A(i,j)$ receives colour
2, every vertex of $A(i,j)$ will be deactivated. So Property (P) is satisfied
for $i$ and $j$.

Now consider the branches where two vertices $x_{1},x_{2}$ of $A(i,j)$ both
received colour 2. We update $A(j,i)$ accordingly. In particular, afterwards
no vertex in $A(j,i)$ is adjacent to $x_{1}$ or $x_{2}$, as $2$ is a colour in
the list of each vertex of $A(j,i)$. We now do some further branching for
those branches where $A(j,i)\neq\emptyset$. We consider the possibility where
each vertex of $N(A(j,i))\cap A_{2}$ is given the colour of $v_{j}$ and all
possibilities where we choose one vertex in $N(A(j,i))\cap A_{2}$ to receive a
colour different from the colour of $v_{j}$ (we consider both options to
colour such a vertex). This leads to $O(n)$ branches. In the first branch,
every vertex of $A(j,i)$ will be deactivated. So Property (P) is satisfied for
$i$ and $j$.

Now consider a branch where a vertex $u\in N(A(j,i))\cap A_{2}$ receives a
colour different from the colour of $v_{j}$. We will show that also in this
case every vertex of $A(j,i)$ will be deactivated. For contradiction, assume
that $A(j,i)$ contains a vertex $w$ that is not deactivated after colouring
$u$. As $u$ was in $N(A(j,i))\cap A_{2}$, we find that $u$ had a neighbour
$w^{\prime}\in A(j,i)$. As $u$ is coloured with a colour different from the
colour of $v_{j}$, the size of $L(w^{\prime})$ is reduced by one (due to Rule
4). Hence $w^{\prime}$ got deactivated after colouring $u$, and thus
$w^{\prime}\neq w$. As $w$ is still active, $w$ has a neighbour $u^{\prime}\in
A_{2}$. As $u^{\prime}$ and $w$ are still active, $u^{\prime}$ and $w$ are not
adjacent to $w^{\prime}$ or $u$. Hence, $u,w^{\prime},v_{j},w,u^{\prime}$
induce a $P_{5}$ in $G$. As $x_{1}$ and $x_{2}$ both received colour 2, we
find that $x_{1}$ and $x_{2}$ are not adjacent to each other. Hence,
$x_{1},v_{i},x_{2}$ induce a $P_{3}$ in $G$. Recall that all vertices of
$A(j,i)$, so also $w$ and $w^{\prime}$, are not adjacent to $x_{1}$ or
$x_{2}$. As $u$ and $u^{\prime}$ were still active after colouring $x_{1}$ and
$x_{2}$, we find that $u$ and $u^{\prime}$ are not adjacent to $x_{1}$ or
$x_{2}$ either. By definition of $A(j,i)$, $w$ and $w^{\prime}$ are not
adjacent to $v_{i}$. By definition of $A(i,j)$, $x_{1}$ and $x_{2}$ are not
adjacent to $v_{j}$. Moreover, $v_{i}$ and $v_{j}$ are non-adjacent, as
$j-i\geq 2$. We conclude that $G$ contains an induced $P_{3}+P_{5}$, namely
with vertex set
$\\{x_{1},v_{i},x_{2}\\}\cup\\{u,w^{\prime},v_{j},w,u^{\prime}\\}$, a
contradiction (see Figure 2 for an example of such a situation). Hence, every
vertex of $A(j,i)$ is deactivated. So Property (P) is satisfied for $i$ and
$j$ also for these branches.

Finally by recursive application of the above described procedure for all
pairs $v_{i},v_{j}$ such that $1\leq i\leq j\leq 7$ and $j-i\geq 2$ we get a
graph satisfying Property (P), which together leads to
$O\bigl{(}n^{\bigl{(}3\cdot\left(\binom{7}{2}-6\right)\bigr{)}}\bigr{)}=O(n^{45})$
branches.

[mode=image,scale=0.9]fig_phase2

Figure 2: The situation in Branching II.

We now consider each resulting instance from Branching II. We denote such an
instance by $(G,L)$ again. Note that vertices from $N_{2}$ may now belong to
$N_{3}$, as their neighbours in $N_{1}$ may have been removed due to the
branching. The exhaustive application of Rules 1– 11 preserves (P) (where we
apply Rule 11 only after applying Rules 1–10 exhaustively). Hence $(G,L)$
satisfies (P).

We observe that if two vertices in $A_{1}$ have a different list, then they
must be adjacent to different vertices of $N_{0}$. Hence, by Property (P), at
most two lists of $\\{\\{1,2\\},\\{1,3\\},\\{2,3\\}\\}$ can occur as lists of
vertices of $A_{1}$. Without loss of generality this leads to two cases:
either every vertex of $A_{1}$ has list $\\{1,2\\}$ or $\\{1,3\\}$ and both
lists occur on $A_{1}$; or every vertex of $A_{1}$ has list $\\{1,2\\}$ only.
In the next phase of our algorithm we reduce, via some further branching,
every instance of the first case to a polynomial number of smaller instances
of the second case.

### Phase 3. Reduce to the case where vertices of $\mathbf{A_{1}}$ have the
same list

Recall that we assume that every vertex of $A_{1}$ has list $\\{1,2\\}$ or
$\\{1,3\\}$. In this phase we deal with the case when both types of lists
occur in $A_{1}$. We first prove the following claim.

######  Claim 8.

Let $i\in\\{1,3,5,7\\}$. Then every vertex from $A_{1}\cap N(v_{i})$ is
adjacent to some vertex $v_{j}$ with $j\not\in\\{i-1,i,i+1\\}$.

Proof of Claim 8. We may assume without loss of generality that $i=1$ or
$i=3$. For contradiction suppose there exists a vertex $w\in A_{1}\cap
N(v_{i})$ that is non-adjacent to all $v_{j}$ with $j\not\in\\{i-1,i,i+1\\}$.
As two consecutive vertices in $N_{0}$ have different colours, no vertex in
$A_{1}$ has two consecutive neighbours in $N_{0}$ due to Rules 4 and 5. Hence
$N(w)\cap N_{0}=\\{v_{i}\\}$. By definition, $w$ has a neighbour $u\in A_{2}$.
If $i=1$, then
$\left\\{u,w,v_{1},v_{2},v_{3}\right\\}\cup\left\\{v_{5},v_{6},v_{7}\right\\}$
induces a $P_{3}+P_{5}$ in $G$. If $i=3$, then
$\left\\{v_{1},v_{2},v_{3},w,u\right\\}\cup\left\\{v_{5},v_{6},v_{7}\right\\}$
induces a $P_{3}+P_{5}$ in $G$. $\diamond$

######  Claim 9.

It holds that $N(A_{1})\cap N_{0}=\\{v_{i-1},v_{i},v_{i+1}\\}$ for some $2\leq
i\leq 6$. Moreover, we may assume without loss of generality that $v_{i-1}$
and $v_{i+1}$ have colour $3$ and both are adjacent to all vertices of $A_{1}$
with list $\\{1,2\\}$, whereas $v_{i}$ has colour $2$ and is adjacent to all
vertices of $A_{1}$ with list $\\{1,3\\}$.

Proof of Claim 9. Recall that lists $\\{1,2\\}$ and $\\{1,3\\}$ both occur on
$A_{1}$. By Property (P), this means that either $N(A_{1})\cap
N_{0}=\\{v_{i-1},v_{i}\\}$ for some $2\leq i\leq 7$ or $N(A_{1})\cap
N_{0}=\\{v_{i-1},v_{i},v_{i+1}\\}$ for some $2\leq i\leq 6$. The case where
$N(A_{1})\cap N_{0}=\\{v_{i-1},v_{i}\\}$ for some $2\leq i\leq 7$ is not
possible due to Claim 8. It follows that $N(A_{1})\cap
N_{0}=\\{v_{i-1},v_{i},v_{i+1}\\}$ for some $2\leq i\leq 6$. We may assume
without loss of generality that $v_{i}$ has colour $2$, meaning that $v_{i-1}$
and $v_{i+1}$ must have colour 3. It follows that every vertex of $A_{1}$ with
list $\\{1,3\\}$ is adjacent to $v_{i}$ but not to $v_{i-1}$ or $v_{i+1}$,
whereas every vertex of $A_{1}$ with list $\\{1,2\\}$ is adjacent to at least
one vertex of $\\{v_{i-1},v_{i+1}\\}$ but not to $v_{i}$. As a vertex of
$A_{1}$ with list $\\{1,3\\}$ has $v_{i}$ as its only neighbour in $N_{0}$, it
follows from Claim 8 that $i$ is an even number. This means that $i-1$ is odd.
Hence, every vertex of $A_{1}$ with list $\\{1,2\\}$ is in fact adjacent to
both $v_{i-1}$ and $v_{i+1}$ due to Claim 8. $\diamond$

By Claim 9, we can partition the set $A_{1}$ into two (non-empty) sets
$X_{1,2}$ and $X_{1,3}$, where $X_{1,2}$ is the set of vertices in $A_{1}$
with list $\\{1,2\\}$ whose only neighbours in $N_{0}$ are $v_{i-1}$ and
$v_{i+1}$ (which both have colour 3) and $X_{1,3}$ is the set of vertices in
$A_{1}$ with list $\\{1,3\\}$ whose only neighbour in $N_{0}$ is $v_{i}$
(which has colour 2).

Our goal is to show that we can branch into at most $O(n^{2})$ smaller
instances, in which either $X_{1,2}=\emptyset$ or $X_{1,3}=\emptyset$, such
that $(G,L)$ is a yes-instance of List 3-Colouring if and only if at least one
of these smaller instances is a yes-instance. Then afterwards it suffices to
show how to deal with the case where all vertices in $A_{1}$ have the same
list in polynomial time; this will be done in Phase 4 of the algorithm. We
start with the following $O(n)$ branching procedure (in each of the branches
we may do some further $O(n)$ branching later on).

Branching III ($O(n)$ branches)
We branch by considering the possibility of giving each vertex in $X_{1,2}$
colour 2 and all possibilities of choosing a vertex in $X_{1,2}$ and giving it
colour 1. This leads to $O(n)$ branches. In the first branch we obtain
$X_{1,2}=\emptyset$. Hence we can start Phase 4 for this branch. We now
consider every branch in which $X_{1,2}$ and $X_{1,3}$ are both nonempty. For
each such branch we will create $O(n)$ smaller instances of List 3-Colouring,
where $X_{1,3}=\emptyset$, such that $(G,L)$ is a yes-instance of List
3-Colouring if and only if at least one of the new instances is a yes-
instance.

Let $w\in X_{1,2}$ be the vertex that was given colour 1 in such a branch.
Although by Rule 4 vertex $w$ will need to be removed from $G$, we make an
exception by temporarily keeping $w$ after we coloured it. The reason is that
the presence of $w$ will be helpful for analysing the structure of $(G,L)$
after Rules 1–11 have been applied exhaustively (where we apply Rule 11 only
after applying Rules 1–10 exhaustively). In order to do this, we first show
the following three claims.

######  Claim 10.

Vertex $w$ is not adjacent to any vertex in $A_{2}\cup X_{1,2}\cup X_{1,3}$.

Proof of Claim 10. By giving $w$ colour 1, the list of every neighbour of $w$
in $A_{2}$ has been reduced by one due to Rule 5. Hence, all neighbours of $w$
in $A_{2}$ are deactivated. For the same reason all neighbours of $w$ in
$X_{1,2}$, which have list $\\{1,2\\}$, are coloured 2, and all neighbours of
$w$ in $X_{1,3}$, which have list $\\{1,3\\}$, are coloured 3. These vertices
were removed from the graph by Rule 4. This proves the claim. $\diamond$

######  Claim 11.

The graph $G[X_{1,3}\cup(N(X_{1,3})\cap A_{2})\cup N_{3}]$ is the disjoint
union of one or more complete graphs, each of which consists of either one
vertex of $X_{1,3}$ and at most two vertices of $A_{2}$, or one vertex of
$N_{3}$.

Proof of Claim 11. We write $G^{*}=G[X_{1,3}\cup(N(X_{1,3})\cap A_{2})\cup
N_{3}]$ and first show that $G^{*}$ is the disjoint union of one or more
complete graphs. For contradiction, assume that $G^{*}$ is not such a graph.
Then $G^{*}$ contains an induced $P_{3}$, say on vertices $u_{1},u_{2},u_{3}$
in that order. As $w\in X_{1,2}\subseteq N_{1}$, we find that $w$ is not
adjacent to any vertex of $N_{3}$. By Claim 10, we find that $w$ is not
adjacent to any vertex of $A_{2}\cup X_{1,3}$. Recall that $v_{i-1}$ and
$v_{i+1}$ are the only neighbours of $w$ in $N_{0}$, whereas $v_{i}$ is the
only neighbour of the vertices of $X_{1,3}$ in $N_{0}$. Hence,
$\\{u_{1},u_{2},u_{3}\\}\cup\\{v_{1},\ldots,v_{i-1},w,v_{i+1},\ldots,v_{7}\\}$
induces a $P_{3}+P_{7}$. This contradicts the $(P_{3}+P_{5})$-freeness of $G$.
We conclude that $G^{*}$ is the disjoint union of one or more complete graphs.

As $G$ is $K_{4}$-free, the above means that every connected component of
$G^{*}$ is a complete graph on at most three vertices, No vertex of $N_{3}$ is
adjacent to a vertex in $X_{1,3}\subseteq N_{1}$. Moreover, by definition,
every vertex of $N(X_{1,3})\cap A_{2}$ is adjacent to at least one vertex of
$X_{1,3}$. As every connected component of $G^{*}$ is a complete graph, this
means that no vertex of $N_{3}$ is adjacent to a vertex of $N(X_{1,3})\cap
A_{2}$ either. We conclude that the vertices of $N_{3}$ are isolated vertices
of $G^{*}$.

Let $D$ be a connected component of $G^{*}$ that does not contain a vertex of
$N_{3}$. From the above we find that $D$ is a complete graph on at most three
vertices. By definition, every vertex in $X_{1,3}$ has a neighbour in $A_{2}$
and every vertex of $N(X_{1,3})\cap A_{2}$ has a neighbour in $X_{1,3}$. This
means that $D$ either consists of one vertex in $X_{1,3}$ and at most two
vertices of $A_{2}$, or $D$ consists of two vertices of $X_{1,3}$ and one
vertex of $A_{2}$. We claim that the latter case is not possible. For
contradiction, assume that $D$ is a triangle that consists of three vertices
$s,u_{1},u_{2}$, where $s\in A_{2}$ and $u_{1},u_{2}\in X_{1,3}$. However, as
$L(u_{1})=L(u_{2})=\\{1,3\\}$, we find that $|L(s)|=1$ by Rule 8,
contradicting the fact that $s$ belongs to $A_{2}$. This completes the proof
of the claim. $\diamond$

######  Claim 12.

For every pair of adjacent vertices $s,t$ with $s\in A_{2}$ and $t\in N_{2}$,
either $t$ is adjacent to $w$, or $N(s)\cap X_{1,3}\subseteq N(t)$.

Proof of Claim 12. For contradiction, assume that $t$ is not adjacent to $w$
and that there is a vertex $r\in X_{1,3}$ that is adjacent to $s$ but not to
$t$. By Claim 10, we find that $w$ is not adjacent to $r$ or $s$. Just as in
the proof of Claim 11, we find that $\\{r,s,t\\}$ together with
$\\{v_{1},,\ldots,v_{i-1},w,v_{i+1},\ldots,v_{7}\\}$ induces a $P_{3}+P_{7}$
in $G$, a contradiction. $\diamond$

We now continue as follows. Recall that $X_{1,3}\neq\emptyset$. Hence there
exists a vertex $s\in A_{2}$ that has a neighbour $r\in X_{1,3}$. As $s\in
A_{2}$, we have that $|L(s)|=3$. Then, by Rule 10, we find that $s$ has at
least two neighbours $t$ and $t^{\prime}$ not equal to $r$. By Claim 11, we
find that neither $t$ nor $t^{\prime}$ belongs to $X_{1,3}\cup N_{3}$. We are
going to fix an induced 3-vertex path $P^{s}$ of $G$, over which we will
branch, in the following way.

If $t$ and $t^{\prime}$ are not adjacent, then we let $P^{s}$ be the induced
path in $G$ with vertices $t,s,t^{\prime}$ in that order. Suppose that $t$ and
$t^{\prime}$ are adjacent. As $G$ is $K_{4}$-free and $s$ is adjacent to
$r,t,t^{\prime}$, at least one of $t,t^{\prime}$ is not adjacent to $r$. We
may assume without loss of generality that $t$ is not adjacent to $r$.

First assume that $t\in N_{2}$. Recall that $s$ has a neighbour in $X_{1,3}$,
namely $r$, and that $r$ is not adjacent to $t$. We then find that $t$ must be
adjacent to $w$ by Claim 12. As $s\in A_{2}$, we find that $s$ is not adjacent
to $w$ by Claim 10. In this case we let $P^{s}$ be the induced path in $G$
with vertices $s,t,w$ in that order.

Now assume that $t\notin N_{2}$. Recall that $t\notin N_{3}$. Hence, $t$ must
be in $N_{1}$. Then, as $t\notin X_{1,3}$ but $t$ is adjacent to a vertex in
$A_{2}$, namely $s$, we find that $t\in X_{1,2}$. Recall that
$t^{\prime}\notin X_{1,3}$. If $t^{\prime}\in N_{1}$ then the fact that
$t^{\prime}\notin X_{1,3}$, combined with the fact that $t^{\prime}$ is
adjacent to $s\in A_{2}$, implies that $t^{\prime}\in X_{1,2}$. However, by
Rule 8 applied on $s,t,t^{\prime}$, vertex $s$ would have a list of size 1
instead of size 3, a contradiction. Hence, $t^{\prime}\notin N_{1}$. As
$t^{\prime}\notin N_{3}$, this means that $t^{\prime}\in N_{2}$. If
$t^{\prime}$ is adjacent to $r$, then $t\in X_{1,2}$ with $L(t)=\\{1,2\\}$ and
$r\in X_{1,3}$ with $L(r)=\\{1,3\\}$ would have the same lists by Rule 6
applied on $r,s,t,t^{\prime}$, a contradiction. Hence $t^{\prime}$ is not
adjacent to $r$. Then, by Claim 12, we find that $t^{\prime}$ must be adjacent
to $w$. Note that $s$ is not adjacent to $w$ due to Claim 10. In this case we
let $P^{s}$ be the induced path in $G$ with vertices $s,t^{\prime},w$ in that
order.

We conclude that either $P^{s}=tst^{\prime}$ or $P^{s}=stw$ or
$P^{s}=st^{\prime}w$. We are now ready to apply another round of branching.

Branching IV ($O(n)$ branches)
We branch by considering the possibility of removing colour 2 from the list of
each vertex in $N(X_{1,3})\cap A_{2}$ and all possibilities of choosing a
vertex in $N(X_{1,3})\cap A_{2}$ and giving it colour 2. In the branch where
we removed colour 2 from the list of every vertex in $N(X_{1,3})\cap A_{2}$,
we obtain that $X_{1,3}=\emptyset$. Hence for that branch we can enter Phase
4. Now consider a branch, where we gave some vertex $s\in N(X_{1,3})\cap
A_{2}$ colour 2. Let $P^{s}=tst^{\prime}$ or $P^{s}=stw$ or
$P^{s}=st^{\prime}w$. We do some further branching by considering all
possibilities of colouring the vertices of $P^{s}$ that are not equal to the
already coloured vertices $s$ and $w$ (should $w$ be a vertex of $P^{s}$) and
all possibilities of giving a colour to the vertex from $N(s)\cap X_{1,3}$
(recall that by Claim 11, $|N(s)\cap X_{1,3}|=1$). This leads to a total of
$O(n)$ branches. We claim that in each of these branches, the size of
$X_{1,3}$ has reduced to at most 1.

[mode=image,scale=0.9]fig_phase3_path2

Figure 3: The situation in Branching IV if $t_{1}\in N_{1}$ and if vertices
$s_{a}$ and $s_{b}$ exist.

For contradiction, assume that there exists a branch where $X_{1,3}$ contains
two vertices $y$ and $y^{\prime}$. Let $s_{a}$ and $s_{b}$ be the neighbours
of $y$ and $y^{\prime}$ in $A_{2}$, respectively. By Claim 11, the graph
induced by $\\{y,y^{\prime},s_{a},s_{b}\\}$ is isomorphic to $2P_{2}$. Hence,
the set $\\{s_{a},y,v_{i},y^{\prime},s_{b}\\}$ induces a $P_{5}$ in $G$.
Recall that $P^{s}=tst^{\prime}$ or $P^{s}=stw$ or $P^{s}=st^{\prime}w$. As
$s_{a}$ and $s_{b}$ have a list of size 3, neither $s_{a}$ nor $s_{b}$ is
adjacent to a vertex of $P^{s}$ due to rule 5. By Claims 10 and 11, neither
$y$ nor $y^{\prime}$ is adjacent to $w$ or $s$, respectively. By colouring
$N(s)\cap X_{1,3}$ neither $y$ nor $y^{\prime}$ is adjacent to $s$, too. As
$s$ received colour 2, vertices $t$ and $t^{\prime}$ have received colour 1 or
3 should they belong to $P^{s}$. In that case neither $t$ nor $t^{\prime}$ can
be adjacent to $y$ or $y^{\prime}$, as $L(y)=L(y^{\prime})=\\{1,3\\}$. By
definition, $v_{i}$ is not adjacent to $s$ or $w$. Moreover, $v_{i}$ can only
be adjacent to a vertex from $\\{t_{j},t^{\prime}_{j}\\}$ if that vertex
belonged to $N_{1}$. However, recall that $t$ and $t^{\prime}$ were not in
$X_{1,3}$ while $s$ was an active vertex. Hence if $t$ or $t^{\prime}$
belonged to $N_{1}$, they must have been in $X_{1,2}$ and thus not adjacent to
$v_{i}$. This means that the vertices of $P^{s}$, together with
$\\{s_{a},y,v_{i},y^{\prime},s_{b}\\}$, induce a $P_{3}+P_{5}$ in $G$, a
contradiction (see Figure 3 for an example of such a situation). Thus
$X_{1,3}$ must contain at most one vertex.

Branching V ($O(1)$ branches)
We branch by considering both possibilities of colouring the unique vertex of
$X_{1,3}$. This leads to two new but smaller instances of List 3-Colouring, in
each of which the set $X_{1,3}=\emptyset$. Hence, our algorithm can enter
Phase 4.

### Phase 4. Reduce to a set of instances of 2-List Colouring

Recall that in this stage of our algorithm we have an instance $(G,L)$ in
which every vertex of $A_{1}$ has the same list, say $\\{1,2\\}$. We deal with
this case as follows. First suppose that $H=P_{2}+P_{5}$. Then $G[N_{2}\cup
N_{3}]$ is an independent set, as otherwise two adjacent vertices of
$N_{2}\cup N_{3}$ form, together with $v_{1},\ldots,v_{5}$, an induced
$P_{2}+P_{5}$. Hence, we can safely colour each vertex in $A_{2}$ with colour
3, and afterwards we may apply Theorem 5.

Now suppose that $H=P_{3}+P_{4}$. We first introduce two new rules, which turn
$(G,L)$ into a smaller instance. In Claims 13 and 15 we show that we may
include those rules in our set of propagation rules that we apply implicitly
every time we modify the instance $(G,L)$.

  1. Rule 12

(neighbourhood identification) If $u$ and $v$ are adjacent, $N(v)\subseteq
N[u]$, and $|L(v)|=3$, then identify $N(u)\cap N(v)$ by $w$, set
$L(w):=\bigcap\\{L(x)\;|\;x\in N(u)\cap N(v)\\}$ and remove $v$ from $G$. If
$G$ contains a $K_{4}$, then return no.

######  Claim 13.

Rule 12 is safe for $K_{4}$-free input, takes polynomial time and does not
affect any vertex of $N_{0}$. Moreover, if we have not obtained a no-answer,
then afterwards $G$ is a connected $(H,K_{4})$-free graph, in which we can
define sets $N_{1},N_{2},N_{3},A_{1},A_{2}$ as before.

Proof of Claim 13. Note that by Claim 3, $G$ is $K_{4}$-free before the
application of Rule 12. Hence $N(u)\cap N(v)$ is an independent set. Let $w$
be the new vertex obtained from identifying $N(u)\cap N(v)$. Observe that
every vertex in the common neighbourhood of two adjacent vertices must receive
the same colour. Hence $w$ can be given the same colour as any vertex of
$N(u)\cap N(v)$, which belongs to $\bigcap\\{L(x)\;|\;x\in N(u)\cap N(v)\\}$.
For the reverse direction, we give each vertex $x\in N(u)\cap N(v)$ the colour
of $w$, which belongs to $L(x)$ by definition. As $|L(v)|=3$ and
$N(v)\setminus N(u)=\\{u\\}$, we have a colour available for $v$. The above
means that $(G,L)$ is a no-instance if a $K_{4}$ is created. We conclude that
Rule 12 is safe and either yields a no-instance if a $K_{4}$ was created, or
afterwards we have again that $G$ is $K_{4}$-free.

It is readily seen that applying Rule 12 takes polynomial time and that
afterwards $G$ is still connected. As $|L(v)|=3$, Claim 7 tells us that $v\in
N_{2}$, and thus $N(v)\subseteq N_{1}\cup N_{2}\cup N_{3}$. Thus Rule 12 does
not involve any vertex of $N_{0}$. Hence, as $G$ is connected, we can define
$V=N_{0}\cup N_{1}\cup N_{2}\cup N_{3}$ by Claim 1.

It remains to prove that $G$ is $H$-free after applying Rule 12. For
contradiction, assume that $G$ has an induced subgraph $P+P^{\prime}$
isomorphic to $H$. Then we find that $w\in V(P)\cup V(P^{\prime})$, say $w\in
V(P)$, as otherwise $P+P^{\prime}$ was already an induced subgraph of $G$
before Rule 12 was applied. By the same argument, we find that $w$ is incident
with two edges $wx$ and $wy$ in $P$ that correspond to edges $sx$ and $ty$
with $s\neq t$ in $G$ before Rule 12 was applied. However, then we can replace
$P$ by the path $xsuty$ to find again that $G$ already contained an induced
copy of $H$ before Rule 12 was applied, a contradiction. $\diamond$

Let $u\in A_{2}$. We let $B(u)$ be the set of neighbours of $u$ that have
colour 3 in their list. By Rule 9, there is a vertex $v\in N(u)$ such that
$3\in L(v)$. Vertex $v$ cannot be in $N_{1}$; otherwise the edge $uv$ implies
that $v\in A_{1}$ and thus $v$ would have list $\\{1,2\\}$. This means that
$v$ must be in $N_{2}\cup N_{3}$. Hence we have proven the following claim.

######  Claim 14.

For every $u\in A_{2}$, it holds that $B(u)\neq\emptyset$ and $B(u)\subseteq
N_{2}\cup N_{3}.$

We will use the following rule (in Claim 15 we show that the colour $q$ is
unique).

  1. Rule 13

($\mathbf{A_{2}}$ list-reduction) If a vertex $v\in B(u)$ for some $u\in
A_{2}$ has no neighbour outside $N[u]$, then remove colour $q$ from $L(u)$ for
$q\in L(v)\setminus\\{3\\}$.

######  Claim 15.

Rule 13 is safe, takes polynomial time and does not affect any vertex of
$N_{0}$. Moreover, afterwards $G$ is a connected $(H,K_{4})$-free graph, in
which we can define sets $N_{1},N_{2},N_{3},A_{1},A_{2}$ as before.

Proof of Claim 15. Let $u$ be a vertex in $A_{2}$ for which there exists a
vertex $v\in B(u)$ with no neighbour outside $N[u]$. It is readily seen that
Rule 13 applied on $u$ takes polynomial time, does not affect any vertex of
$N_{0}$, and afterwards we can define sets $N_{1},N_{2},N_{3},A_{1},A_{2}$ as
before.

We recall from above that $v\in N_{2}\cup N_{3}$. As $N(v)\setminus
N[u]=\emptyset$, we find by Rule 12 that $|L(v)|\neq 3$. Then, by Rule 4, it
holds that $|L(v)|=2$. Thus vertex $v$ has $L(v)=\\{q,3\\}$ for some
$q\in{\\{1,2\\}}$. If there exists a colouring $c$ of $G$ with $c(u)=q$ that
respects $L$, then $c(v)=3$, and so $c$ colours each vertex in $N(v)\cap N(u)$
with a colour from $\left\\{1,2\right\\}$.

We define a colouring $c^{\prime}$ by setting $c^{\prime}(u)=3$,
$c^{\prime}(v)=q$ and $c^{\prime}=c$ for $V(G)\setminus\\{u,v\\}$. We claim
that $c^{\prime}$ also respects $L$. As $N(v)\setminus N[u]=\emptyset$, every
neighbour $w\neq u$ of $v$ is a neighbour of $u$ as well and thus received a
colour $c^{\prime}(w)=c(w)$ that is not equal to colour $q$ (and colour $3$).
As $v\in N_{2}\cup N_{3}$ by Claim 14, all vertices in $N(u)\setminus N[v]$
are in $N_{1}$ by Claim 2. As $u\in A_{2}$, these vertices all belong to
$A_{1}$ and thus their lists are equal to $\\{1,2\\}$, so do not contain
colour 3. Hence, $c^{\prime}$ respects $L$ indeed.

The above means that we can avoid assigning colour $q$ to $u$. We may
therefore remove $q$ from $L(u)$. This completes the proof of the claim.
$\diamond$

We note that if a colour $q$ is removed from the list of some vertex $u\in
A_{2}$ due to Rule 13, then $u$ is no longer active.

Assume that Rules 1–13 have been applied exhaustively. By Rule 2, we find that
$A_{2}\neq\emptyset$. Then we continue as follows. Let $u\in A_{2}$ and $v\in
B(u)$ (recall that $B(u)$ is nonempty due to Claim 14). Let $A(u,v)\subseteq
N_{1}$ be the set of (active) neighbours of $u$ that are not adjacent to $v$.
Note that $A(u,v)\subseteq A_{1}$ by definition. Let $A(v,u)\subseteq N_{1}$
be the set of neighbours of $v$ that are not adjacent to $u$. We claim that
both $A(u,v)$ and $A(v,u)$ are nonempty. By Rule 13, we find that
$A(v,u)\neq\emptyset$. By Rule 12, vertex $u$ has a neighbour $t\notin N(v)$.
As $v\in N_{2}\cup N_{3}$ due to Claim 14, we find by Claim 2 that $t$ belongs
to $N_{1}$, thus $t\in A(u,v)$, and consequently, $A(u,v)\neq\emptyset$. We
have the following three disjoint situations:

  1. 1.

$A(v,u)$ contains a vertex $w$ with $L(w)=\\{1,2\\}$ that is not adjacent to
some vertex $t\in A(u,v)$;

  2. 2.

$A(v,u)$ contain at least one vertex $w$ that is not adjacent to some vertex
$t\in A(u,v)$, but for all such vertices $w$ it holds that
$L(w)\neq\\{1,2\\}$.

  3. 3.

Every vertex in $A(v,u)$ is adjacent to every vertex of $A(u,v)$.

Now we construct a triple $(Q,P,x)=(Q(u),P(u),x(u))$ such that $Q$ is a set
which contains $u$, $P\subseteq Q$ is an induced $P_{4}$ and $x$ is a vertex
of $Q$. In situation 1, we let $Q=\\{w,t,u,v\\}$. We say that $Q$ is of type
1. We let $x=u$. As $P$ we can take the path on vertices $t,u,v,w$ in that
order. In situation 2, we let $Q=\\{w,t,u,v\\}$ for some $w\in A(v,u)$ that is
not adjacent to some $t\in A(u,v)$. We say that $Q$ is of type 2. We let
$x=v$. As $P$ we can take the path on vertices $t,u,v,w$ in that order.

Finally we consider situation 3. By Rule 7 applied on $u$ and a vertex of
$A(v,u)$ we find that $N(u)\cap N(v)$ contains at least one vertex $s$. We let
$Q=\\{s,t,w,u,v\\}$ for some $w\in A(v,u)$ and $t\in A(u,v)$. We let $x=v$. We
claim that the vertices $s,u,t,w$ induce a $P_{4}$ in that order. By
definition, $u$ is not adjacent to $w$. If $sw\in E(G)$, then $L(u)=L(w)$ due
to Rule 6. As $w$ has a list of size 2, $u$ has also a list of size 2. If
$st\in E(G)$, then $L(v)=L(t)$ due to Rule 6. In that case it even holds that
$|L(v)|=|L(t)|=1$, which means that $u$ has a list of size 2 due to Rule 5. In
both cases $u$ is not an active vertex, a contradiction. Hence, as $P$ we can
take the path on vertices $s,u,t,w$ in that order.

We slightly try to extend $Q$ as follows. If $A(u,v)$ contains more vertices
than only vertex $t$, we pick an arbitrary vertex $t^{\prime}$ of
$A(u,v)\setminus\\{t\\}$ and put $t^{\prime}$ to $Q$. We first observe that if
$c(x)=3$ no other vertex of $Q$ can be coloured with colour $3$; in particular
recall that $t$ and $t^{\prime}$ (if $t^{\prime}$ exists) both belong to
$A_{1}$, and as such have list $\\{1,2\\}$. Moreover, if $Q$ is of type 2,
then any vertex in $A(v,u)$ with list $\\{1,2\\}$ is adjacent to $t$ and
$t^{\prime}$, as otherwise $Q$ is of type 1.

Branching VI ($O(n)$ branches)
We choose a vertex $u\in A_{2}$ such that $|N(u)\cap N_{1}|$ is minimal and
create $(Q,P,x)$. We branch by considering all possibilities of colouring $Q$
such that $c(x)=3$ and the possibility where we remove colour $3$ from $L(x)$.
The first case leads to $O(1)$ branches, since $|Q|\leq 6$. We will prove that
we either terminate by Rule 2 or branch in Branching VII. In the second case
we deactivate $u$ directly or by applying Rule 13 and Rule 5. This is the only
recursive branch and the depth of the recursion is $|A_{2}|\in O(n)$.

Now consider a branch where $Q$ is coloured. Although by Rule 4 vertices in
$Q$ will need to be removed from $G$, we make an exception by temporarily
keeping $Q$ in the graph after we coloured it until the end of Branching VII.
The reason is that this will be helpful for analysing the structure of
$(G,L)$. We run only Rules 2, 5 and 8 to prevent changes in the size of
neighbourhood of vertices in $A_{2}$ for the purposes of the next claim (Claim
16). Observe that Rules 2, 5 and 8 do not decrease the degree of any vertex.
By Rule 2, $A_{2}\neq\emptyset$. We prove the following claim for vertices in
$A_{2}$.

######  Claim 16.

There is no vertex in $A_{2}$ with more than one neighbour in $A_{1}$.

Proof of Claim 16. For contradiction, assume that $r$ is a vertex in $A_{2}$
with two neighbours $s$ and $s^{\prime}$ in $A_{1}$. By Rule 8, $s$ and
$s^{\prime}$ are not adjacent. Hence the set $\\{s,r,s^{\prime}\\}$ induces a
$P_{3}$, which we denote by $P^{\prime}$. As every vertex in $A_{1}$ has list
$\\{1,2\\}$, the only possible edges between $Q$ and $P^{\prime}$ are those
between $\\{s,s^{\prime}\\}$ and vertex $x$, the only vertex in $Q$ which has
colour $3$.

First suppose $Q$ is of type 1. Recall that $x=u$. If $|N(u)\cap A_{1}|=1$,
then $u$ cannot have any other vertex in $A_{1}\setminus Q$ as a neighbour. If
$|N(u)\cap A_{1}|\geq 2$, then there has to be an edge to all but one vertex
in $N(r)\cap A_{1}$. This together with at least two coloured vertices in
$Q\cap N(u)\cap N_{1}$ gives a contradiction with the minimality of $|N(u)\cap
N_{1}|$.

Now suppose that $Q$ is of type 2. Recall that $x=v$. Recall also that if $v$
is adjacent to a vertex in $A_{1}\setminus Q$, then this vertex must be
adjacent to another vertex from $Q$ as well, since otherwise $Q$ would be of
type 1. This is not possible since all of them are already coloured by colour
in $\\{1,2\\}$.

Finally, suppose that $Q$ is of type 3. Recall that $x$ is not in $P$, thus
there is no vertex with list $\\{1,2\\}$ adjacent to $P$.

We conclude that in all three cases $Q\cup V(P^{\prime})$, and thus $G$,
contains an induced $P_{3}+P_{4}$, a contradiction. $\diamond$

We now run reduction Rules 1–13 exhaustively (and in the right order). Recall,
however, that we make exception by not erasing $Q$. We continue with Branching
VII.

[mode=image,scale=0.8]fig_branchingVII

Figure 4: The situation in Branching VII. Dashed lines denote edges that might
or might not be there.

Branching VII ($O(n)$ branches)
We branch by considering the possibility of removing colour 3 from the list of
each vertex in $A_{2}$, and all possibilities of choosing one vertex in
$A_{2}$, to which we give colour 3, and all possibilities of colouring its
neighbour in $A_{1}$ (recall that this neighbour is unique due to Claim 16).
This leads to $O(n)$ branches. We show that all of them are instances with no
vertex with list of size three and thus Rule 2 can be applied on them.

In the first branch, all lists have size at most 2 directly by the
construction.

Now consider a branch where a vertex $r\in A_{2}$ and its unique neighbour in
$A_{1}$ were coloured (where $r$ is given colour 3). We make an exception to
Rule 4 and temporarily keep vertex $r$ and all its neighbours in $G$, even if
they need to be removed from $G$ due to our rules.

Denote the vertex in $N(r)\cap A_{1}$ by $r_{1}$. Recall that
$L(r_{1})=\\{1,2\\}$ and that every vertex in $A_{2}$ has exactly one
neighbour in $A_{1}$. Note that $|N(u)\cap A_{1}|$ was equal to 1 before $u$
was coloured. Before assigning a colour to $r$, vertex $r$ had two other
neighbours $r_{2}$ and $r_{3}$ by Rule 10, which were in $N_{2}\cap N_{3}$.
Vertices $r_{1},r,r_{2}$ as well as $r_{1},r,r_{3}$ induce a $P_{3}$,
otherwise there is either a $K_{4}$ or we use Rule 12 on vertex $r$. As $G$ is
$P_{3}+P_{4}$-free, there must be at least one edge between $P$ and
$\\{r_{1},r,r_{2}\\}$ and between $P$ and $\\{r_{1},r,r_{3}\\}$. We first show
that such an edge is not incident to $r_{1}$.

If there exists an edge between $r_{1}$ and a vertex from $P$, then this
vertex must be $x$ (as $L(r_{1})=\\{1,2\\}$). First suppose $Q$ is of type 1.
Then $x=u$. However, $u$ had only one neighbour in $A_{1}$, which is in $Q$, a
contradiction. Now suppose $Q$ is of type 2. Then $x=v$. If $r_{1}$ is
adjacent to $v$, then $r_{1}$ is adjacent to another vertex in $Q$, a
contradiction. Finally suppose that $Q$ is of type 3. Then $x$ in not in $P$.
Thus $r_{1}$ is not adjacent to $P$.

We conclude from the above that there must exist an edge between $r_{2}$ and a
vertex of $P$, and an edge between $r_{3}$ and a vertex of $P$. By Rule 6,
these neighbours of $r_{2}$ and $r_{3}$ must be different. We show that
vertices $r_{2}$ and $r_{3}$ received a colour, since $r_{2}$ and $r_{3}$ have
a different neighbour in $Q$ and thus at least one neighbour has obtained a
colour different from $3$. Since $r$ is coloured by 3, the lists of $r_{2}$
and $r_{3}$ are reduced by Rule 5 to size 1 or the instance is a no-instance.

For sake of contradiction assume that there exists a vertex $z$ with list of
size three, i.e., $z\in A_{2}$. Note that $|N(z)\cap A_{1}|=1$. The same
observations for neighbours of $z$ hold by the same arguments as above.
Namely, vertex $z_{1}\in N(z)\cap A_{1}$ does not have a neighbour in $P$ and
vertices $z_{2},z_{3}$ are in $N_{2}\cup N_{3}$ and they induce two $P_{3}$s:
$z_{1},z,z_{2}$ and $z_{1},z,z_{3}$. Therefore, $z_{2},z_{3}$ each have
different neighbours in $P$, too. Moreover, at least one edge between $r_{1}$
and $z_{2},z_{3}$ is missing by Rule 6. Without loss of generality
$\\{r_{1},z_{2}\\}\notin E$. Then vertices $z_{1},z,z_{2},q$, where $q$ is in
$N(z_{2})\cap V(P)$, induce a new $P_{4}$. Again at least one vertex from
$r_{2},r_{3}$ is not adjacent to $q$, say $r_{2}q\notin E$. As $r_{1}$ and
$r_{2}$ are coloured by 1 or 2, they have no edge to $z_{1}$ and to $z$;
otherwise $z$ and $z_{1}$ are not active by Rule 5. Recall that $r_{1},z_{1}$
have no neighbour in $P$ and that $r$ had only one neighbour in $A_{1}$, thus
$r$ is not adjacent to $z_{1}$. By Claim 6 there are no edges between
$r_{2},r_{3}$ and $z_{2},z_{3}$. Hence $r_{1},r,r_{2}$ together with
$z_{1},z,z_{2},q$ induce a $P_{3}+P_{4}$ in $G$, a contradiction (see Figure 4
for an example of such a situation).

The correctness of our algorithm follows from the above description. It
remains to analyse its running time. The branching is done in seven stages
(Branching I-VII) yielding a total number of $O(n^{49})$ branches. It is
readily seen that processing each branch created in Branching I-VII takes
polynomial time. Hence the total running time of our algorithm is polynomial.
∎

Remark. Except for Phase 4 of our algorithm, all arguments in our proof hold
for $(P_{3}+P_{5})$-free graphs. The difficulty in Phase 4 is that in contrary
to the previous phases we cannot use the vertices from $N_{0}$ to find an
induced $P_{3}+P_{5}$ and therefore obtain the contradiction similarly to the
previous phases.

##  3 Classifying All Graphs ${\mathbf{H}}$ up to Seven Vertices

By combining our new results from Section 2 with known results from the
literature we can now prove Corollary 1.

Corollary 1 (restated). Let $H$ be a graph with $|V(H)\leq 7$. If $H$ is a
linear forest, then List $3$-Colouring is polynomial-time solvable for
$H$-free graphs; otherwise already $3$-Colouring is $\mathsf{NP}$-complete for
$H$-free graphs.

###### Proof.

If $H$ is not a linear forest, then $H$ contains an induced claw or a cycle,
which means that 3-Colouring is $\mathsf{NP}$-complete due to results in [14,
21, 27]. Suppose $H$ is a linear forest. We first recall that List 3-Colouring
is polynomial-time solvable for $P_{7}$-free graphs [7] and thus for
$(rP_{1}+P_{7})$-free graphs for every integer $r\geq 0$ [5, 15]. Now suppose
that $H$ is not an induced subgraph of $rP_{1}+P_{7}$ for any $r\geq 0$. If
$H=P_{1}+3P_{2}$, then the class of $H$-free graphs is a subclass of
$4P_{3}$-free graphs, for which List 3-Colouring is polynomial-time solvable
[5, 15]. Otherwise, $H$ has at least two connected components, all of which
containing at least one edge. This means that
$H\in\\{2P_{2}+P_{3},P_{2}+P_{5},P_{3}+P_{4}\\}$. If $H=2P_{2}+P_{3}$, then
the class of $H$-free graphs is a subclass of $4P_{3}$-free graphs, for which
we just recalled that List 3-Colouring is polynomial-time solvable. The cases
where $H=P_{2}+P_{5}$ and $H=P_{3}+P_{4}$ follow from Theorem 2. ∎

##  4 The Hardness Result

In this section we prove that 5-Colouring is $\mathsf{NP}$-complete for
$(P_{3}+P_{5})$-free graphs. In order to do this we use a reduction from a
variant of Not-All-Equal 3-Satisfiability with positive literals only. This
problem is $\mathsf{NP}$-complete [33] and is defined as follows. Let
$X=\\{x_{1},x_{2},...,x_{n}\\}$ be a set of logical variables, and let ${\cal
C}=\\{C_{1},C_{2},...,C_{m}\\}$ be a set of 3-literal clauses over $X$ in
which all literals are positive. Does there exist a truth assignment for $X$
such that each clause contains at least one true literal and at least one
false literal? We call such a truth assignment satisfying.

From a given instance $({\cal C},X)$ of Not-All-Equal 3-Satisfiability with
positive literals only we construct a graph $G$ with a list assignment $L$ as
follows.

  * •

For each $x_{i}\in X$ we introduce two vertices $x_{i}$ and
$\overline{x_{i}}$, which we make adjacent to each other. We say that $x_{i}$
and $\overline{x}_{i}$ are of $x$-type. We set
$L(x_{i})=L(\overline{x}_{i})=\\{4,5\\}$.

  * •

For each $C_{j}\in{\cal C}$ we introduce a vertex $C_{j}$ and a vertex
$C_{j}^{\prime}$ called the copy of $C_{j}$. We say that $C_{j}$ and
$C_{j}^{\prime}$ are of $C$-type. We set
$L(C_{j})=L(C_{j}^{\prime})=\\{1,2,3\\}$.

  * •

We add an edge between each $x$-type vertex and each $C$-type vertex.

  * •

For each $C_{j}\in{\cal C}$ we do as follows. We fix an arbitrary order of the
literals in $C_{j}$. Say $C_{j}=\\{x_{g},x_{h},x_{i}\\}$ in that order. Then
we add six vertices $a_{g,j}$, $a_{h,j}$, $a_{i,j}$, $a_{g,j}^{\prime}$,
$a_{h,j}^{\prime}$, $a_{i,j}^{\prime}$ and edges $x_{g}a_{g,j}$,
$a_{g,j}C_{j}$, $x_{h}a_{h,j}$, $a_{h,j}C_{j}$, $x_{i}a_{i,j}$, $a_{i,j}C_{j}$
and also edges $\overline{x}_{g}a_{g,j}^{\prime}$,
$a_{g,j}^{\prime}C_{j}^{\prime}$, $\overline{x}_{h}a_{h,j}^{\prime}$,
$a_{h,j}^{\prime}C_{j}^{\prime}$, $\overline{x}_{i}a_{i,j}^{\prime}$,
$a_{i,j}^{\prime}C_{j}^{\prime}$. We say that $a_{g,j}$, $a_{h,j}$, $a_{i,j}$,
$a_{g,j}^{\prime}$, $a_{h,j}^{\prime}$, $a_{i,j}^{\prime}$ are of $a$-type. We
set $L(a_{g,j})=L(a_{g,j}^{\prime})=\\{1,4\\}$,
$L(a_{h,j})=L(a_{h,j}^{\prime})=\\{2,4\\}$ and
$L(a_{i,j})=L(a_{i,j}^{\prime})=\\{3,4\\}$.

######  Lemma 1.

$({\cal C},X)$ has a satisfying truth assignment if and only if $G$ has a
colouring that respects $L$.

###### Proof.

First suppose that $({\cal C},X)$ has a satisfying truth assignment $\tau$.
For each $x_{i}\in X$ we do as follows. If $\tau(x_{i})$ is true then we give
$x_{i}$ colour 4; otherwise we give $x_{i}$ colour 5. In the first case we
give $\overline{x}_{i}$ colour 5, and in the second case we give
$\overline{x}_{i}$ colour 4. If $x_{i}$ belongs to $C_{j}$, then the vertices
$a_{i,j}$ and $a_{i,j}^{\prime}$ exist, say
$L(a_{i,j})=L(a_{i,j}^{\prime})=\\{\ell,4\\}$ for some $\ell\in\\{1,2,3\\}$.
We give $a_{i,j}$ colour $\ell$ if $x_{i}$ has colour 4, and we give $a_{i,j}$
colour 4 if $x_{i}$ has colour 5. We give $a_{i,j}^{\prime}$ colour $\ell$ if
$\overline{x}_{i}$ has colour 4, and we give $a_{i,j}^{\prime}$ colour 4 if
$\overline{x}_{i}$ has colour 5. Consider an (ordered) clause
$C_{j}=\\{x_{g},x_{h},x_{i}\\}$. As $\tau$ is a satisfying truth assignment,
at least one of $x_{g},x_{h},x_{i}$, say $x_{g}$, has colour 4 (and thus
$\overline{x}_{g}$ has colour 5) and at least one of $x_{g},x_{h},x_{i}$, say
$x_{h}$, has colour 5. Hence, vertices $a_{g,j}^{\prime}$ and $a_{h,j}$ have
colour 4, which means we can safely colour $C_{j}$ and $C_{j}^{\prime}$ with
colours 2 and 1, respectively. Hence, in the end we obtain a colouring of $G$
that respects $L$.

Now suppose that $G$ has a colouring that respects $L$. Consider an (ordered)
clause $C_{j}=\\{x_{g},x_{h},x_{i}\\}$. If $x_{g},x_{h},x_{i}$ are all
coloured 4, then $a_{g,j}$, $a_{h,j}$, $a_{i,j}$ must have colours $1,2,3$,
respectively, which is a contradiction, as in that case $C_{j}$ cannot have a
colour. If $x_{g},x_{h},x_{i}$ are all coloured 5, then
$\overline{x}_{g},\overline{x}_{h},\overline{x}_{i}$ are all coloured 4, and
we obtain the same contradiction by considering $C_{j}^{\prime}$ instead.
Hence, at least one of $x_{g},x_{h},x_{i}$ must have colour 4 and at least one
of $x_{g},x_{h},x_{i}$ must have colour 5. This means that the truth
assignment that sets a variable $x_{i}$ true if $x_{i}$ has colour 4 and false
if $x_{i}$ has colour 5 is a satisfying truth assignment of $({\cal C},X)$. ∎

We now extend $G$ into a graph $G^{\prime}$ by adding a clique consisting of
five new vertices $k_{1},\ldots,k_{5}$, which we say are of $k$-type, and by
adding an edge between a vertex $k_{\ell}$ and a vertex $u\in V(G)$ if and
only if $\ell\notin L(u)$. See Figure 5 for an illustration.

[mode=image,scale=0.7]fig_hardness

Figure 5: An example of the graph $G^{\prime}$, where
$C_{j}=(x_{h},x_{i},x_{j})$ in that order.

######  Lemma 2.

$({\cal C},X)$ has a satisfying truth assignment if and only if $G^{\prime}$
has a $5$-colouring.

###### Proof.

By Lemma 1 it suffices to show that $G$ has a colouring that respects $L$ if
and only if $G^{\prime}$ has a 5-colouring. First suppose that $G$ has a
colouring that respects $L$. Then we can extend this colouring to a
5-colouring of $G^{\prime}$ by giving $k_{\ell}$ colour $\ell$ for
$\ell=1,\ldots,5$. Now suppose that $G^{\prime}$ has a 5-colouring. Then, as
the $k$-type vertices form a clique, we may assume without loss of generality
that $k_{\ell}$ has colour $\ell$ for $\ell=1,\ldots,5$. This means that the
restriction of the 5-colouring of $G^{\prime}$ to $G$ is a colouring that
respects $L$. ∎

######  Lemma 3.

The graph $G^{\prime}$ is $(P_{3}+P_{5})$-free.

###### Proof.

For contradiction, assume that $G^{\prime}$ has an induced subgraph $H$
isomorphic to $P_{3}+P_{5}$. We say that $H$ consists of a $P_{3}$-component
and a $P_{5}$-component.

First suppose that $H$ contains no $x$-type vertex and no $C$-type vertex.
However, as the $k$-type vertices and $a$-type vertices induce a $2P_{2}$-free
graph, this is not possible. Now suppose that $H$ contains an $x$-type vertex
and a $C$-type vertex. As these two vertices are adjacent, they belong to the
same connected component of $H$. As every $x$-type vertex is adjacent to
$k_{1}$, $k_{2}$, $k_{3}$ and every $C$-type vertex is adjacent to $k_{4}$ and
$k_{5}$, this means that the other connected component of $H$ can only
contains $a$-type vertices. However, the $a$-type vertices form an independent
set. So this is not possible either. We conclude that $H$ either contains at
least one $C$-type vertex and no $x$-type vertices, or the other way around.

Case 1. $H$ contains at least one $C$-type vertex and no $x$-type vertices.
We note that the $C$-type vertices and $a$-type vertices induce a disjoint
union of stars, so they induce a $P_{5}$-free graph. Hence $H$ must contain at
least one $k$-type vertex. As $k$-type vertices form a clique, $H$ can contain
at most two of them, which must belong to the $P_{5}$-component of $H$ (due to
the above observation that the graph induced by $C$-type and $a$-type vertices
is $P_{5}$-free). As every $a$-type vertex has exactly one $C$-type neighbour,
this means that the $P_{3}$-component of $H$ is of the form $a-C-a$. Every
$C$-type vertex is adjacent to $k_{4}$ and $k_{5}$. Hence the $k$-type
vertices of the $P_{5}$-component of $H$ belong to $\\{k_{1},k_{2},k_{3}\\}$.
Every $a$-type vertex is adjacent to two vertices of $\\{k_{1},k_{2},k_{3}\\}$
and to $k_{5}$. As two $a$-type neighbours of a $C$-type vertex have exactly
one common neighbour in $\\{k_{1},k_{2},k_{3}\\}$, this means that the
$P_{5}$-component of $H$ cannot contain any $k$-type vertex, a contradiction.

Case 2. $H$ contains at least one $x$-type vertex and no $C$-type vertices.
First suppose that the $P_{3}$-component of $H$ contains two adjacent $x$-type
vertices. All $x$-type vertices have the same $k$-type neighbours. Moreover,
any $a$-type vertex has exactly one $x$-type neighbour. Hence, the
$P_{3}$-component is of the form $a-x-x$. As every $a$-type vertex is adjacent
to $k_{5}$, and every $x$-type vertex is adjacent to every vertex of
$\\{k_{1},k_{2},k_{3}\\}$, the $P_{5}$-component of $H$ contains at most one
$k$-type vertex, which must be $k_{4}$. However, $k_{4}$ is not adjacent to
any $a$-type or $x$-type vertex, so this is not possible. Hence, the
$P_{5}$-component of $H$ only contains $a$-type and $x$-type vertices. This is
not possible either, as the graph induced by the $a$-type and $x$-type
vertices is a disjoint union of split graphs (or, more precisely, double
stars), so this graph is $P_{5}$-free. We conclude that the $P_{3}$-component
of $H$ cannot contain any two adjacent $x$-type vertices.

Now suppose that the $P_{5}$-component of $H$ contains two adjacent $x$-type
vertices. As every $a$-type vertex has exactly one $x$-type neighbour and two
$x$-type vertices have exactly the same $k$-type neighbours, the
$P_{5}$-component of $H$ is of the form $a-x-x-a-k$ or $x-x-a-k-a$ or $x-x-a-
k-k$, where the $k$-type vertex or vertices must be in $\\{k_{4},k_{5}\\}$.
The latter observation, combined with the fact that two $a$-type vertices are
both adjacent to $k_{5}$ and non-adjacent to $k_{4}$, implies that the
$P_{5}$-component of $H$ is of the form $x-x-a-k-a$ or $x-x-a-k-k$ and
contains $k_{5}$. As the $k$-type vertices form a clique, this means that the
$P_{3}$-component of $H$ contains no $k$-type vertices. As the $a$-type
vertices are all adjacent to $k_{5}$, the $P_{3}$-component of $H$ contains no
$a$-type vertices either. Hence the $P_{3}$-component of $H$ only consists of
$x$-type vertices. As the graph induced by the $x$-type vertices is a disjoint
union of $P_{2}$s, we obtain a contradiction.

Finally suppose that $H$ contains no two adjacent $x$-type vertices. Recall
that the $a$-type vertices and $x$-type vertices induce a $P_{5}$-free graph.
Hence, the $P_{5}$-component of $H$ must contain at least one $k$-type vertex.
As the $k$-type vertices form a clique, the $P_{3}$-component of $H$ contains
no $k$-type vertex implying that it is of the form $a-x-a$. We recall that
every $x$-type vertex is adjacent to $k_{1}$, $k_{2}$, $k_{3}$ and that every
$a$-type vertex is adjacent to $k_{5}$. This means that the $P_{5}$-component
of $H$ contains only one $k$-type vertex, which must be $k_{4}$. However, as
$k_{4}$ is not adjacent to any $x$-type or $a$-type vertex, this is not
possible. ∎

We observe that $5$-Colouring belongs to $\mathsf{NP}$. Hence, by Lemmas 2 and
3 we obtain Theorem 3.

Theorem 3 (restated). $5$-Colouring is $\mathsf{NP}$-complete for
$(P_{3}+P_{5})$-free graphs.

##  5 Conclusions

By solving two new cases we completed the complexity classifications of
$3$-Colouring and List $3$-Colouring on $H$-free graphs for graphs $H$ up to
seven vertices. We showed that both problems become polynomial-time solvable
if $H$ is a linear forest, but stay $\mathsf{NP}$-complete in all other cases.
Recall that $k$-Colouring $(k\geq 3)$ is $\mathsf{NP}$-complete on $H$-free
graphs whenever $H$ is not a linear forest. For the case where $H$ is a linear
forest, our new $\mathsf{NP}$-hardness result for 5-Colouring for
$(P_{3}+P_{5})$-free graphs bounds, together with the known
$\mathsf{NP}$-hardness results of [22] for 4-Colouring for $P_{7}$-free graphs
and 5-Colouring for $P_{6}$-free graphs, the number of open cases of
$k$-Colouring from above.

For future research we aim to our extend our results. For instance, is there
an integer $k\geq 4$ such that $k$-Colouring is $\mathsf{NP}$-complete for
$(P_{2}+P_{5})$-free graphs? It also remains to determine the complexity of
3-Colouring for $(P_{3}+P_{5})$-free graphs. In fact we still do not know if
there exists a linear forest $H$ such that $3$-Colouring is
$\mathsf{NP}$-complete for $H$-free graphs. This is, however, a notorious open
problem studied in many papers; for a recent discussion see [17]. It is also
open for List 3-Colouring, where an affirmative answer to one of the two
problems yields an affirmative answer to the other one [16]. For $k\geq 4$, we
emphasize that all open cases involve linear forests $H$ whose connected
components are small. For instance, if $H$ has at most six vertices, then the
polynomial-time algorithm for 4-Precolouring Extension on $P_{6}$-free graphs
[8, 9] implies that there are only three graphs $H$ with $|V(H)|\leq 6$ for
which we do not know the complexity of 4 Colouring on $H$-free graphs, namely
$H\in\\{P_{1}+P_{2}+P_{3},P_{2}+P_{4},2P_{3}\\}$ (see [15]).

The main difficulty to extend the known complexity results is that hereditary
graph classes characterized by a forbidden induced linear forest are still not
sufficiently well understood due to their rich structure (proofs of
algorithmic results for these graph classes are therefore often long and
technical; see also, for example, [3, 8, 9]). We need a better understanding
of these graph classes in order to make further progress. This is not only the
case for the two colouring problems in this paper. For example, the
Independent Set problem is known to be polynomial-time solvable for
$P_{6}$-free graphs [19], but it is not known if there exists a linear forest
$H$, such that it is $\mathsf{NP}$-complete for $H$-free graphs. A similar
situation holds for Odd Cycle Transversal and Feedback Vertex Set and a whole
range of other problems; see [2] for a survey.

Acknowledgments. We thank Karel Král for pointing out a mistake in a
preliminary version of our paper.

## References

  * [1] Noga Alon.  Restricted colorings of graphs.  Surveys in combinatorics, London Mathematical Society Lecture Note Series, 187:1–33, 1993.
  * [2] Marthe Bonamy, Konrad K. Dabrowski, Carl Feghali, Matthew Johnson, and Daniël Paulusma.  Independent feedback vertex set for ${P}_{5}$-free graphs.  Algorithmica, to appear.
  * [3] Flavia Bonomo, Maria Chudnovsky, Peter Maceli, Oliver Schaudt, Maya Stein, and Mingxian Zhong.  Three-coloring and list three-coloring of graphs without induced paths on seven vertices.  Combinatorica, (in press).
  * [4] Hajo Broersma, Fedor V. Fomin, Petr A. Golovach, and Daniël Paulusma.  Three complexity results on coloring $P_{k}$-free graphs.  European Journal of Combinatorics, 34(3):609–619, 2013.
  * [5] Hajo Broersma, Petr A. Golovach, Daniël Paulusma, and Jian Song.  Updating the complexity status of coloring graphs without a fixed induced linear forest.  TCS, 414(1):9–19, 2012.
  * [6] Maria Chudnovsky.  Coloring graphs with forbidden induced subgraphs.  Proc. ICM 2014, IV:291–302, 2014.
  * [7] Maria Chudnovsky, Peter Maceli, Juraj Stacho, and Mingxian Zhong.  4-Coloring $P_{6}$-free graphs with no induced 5-cycles.  Journal of Graph Theory, 84(3):262–285, 2017.
  * [8] Maria Chudnovsky, Sophie Spirkl, and Mingxian Zhong.  Four-coloring ${P}_{6}$-free graphs. I. Extending an excellent precoloring.  CoRR, 1802.02282, 2018.
  * [9] Maria Chudnovsky, Sophie Spirkl, and Mingxian Zhong.  Four-coloring ${P}_{6}$-free graphs. II. Finding an excellent precoloring.  CoRR, 1802.02283, 2018.
  * [10] Maria Chudnovsky and Juraj Stacho.  3-colorable subclasses of $P_{8}$-free graphs.  Man., 2017.
  * [11] Jean-François Couturier, Petr A. Golovach, Dieter Kratsch, and Daniël Paulusma.  List coloring in the absence of a linear forest.  Algorithmica, 71(1):21–35, 2015.
  * [12] Konrad K. Dabrowski and Daniël Paulusma.  On colouring $(2{P}_{2},{H})$-free and $({P}5,{H})$-free graphs.  Information Processing Letters, 131:26–32, 2018.
  * [13] Keith Edwards.  The complexity of colouring problems on dense graphs.  TCS, 43:337–343, 1986.
  * [14] Thomas Emden-Weinert, Stefan Hougardy, and Bernd Kreuter.  Uniquely colourable graphs and the hardness of colouring graphs of large girth.  Combinatorics, Probability and Computing, 7(04):375–386, 1998.
  * [15] Petr A. Golovach, Matthew Johnson, Daniël Paulusma, and Jian Song.  A survey on the computational complexity of colouring graphs with forbidden subgraphs.  Journal of Graph Theory, 84(4):331–363, 2017.
  * [16] Petr A. Golovach, Daniël Paulusma, and Jian Song.  Closing complexity gaps for coloring problems on $H$-free graphs.  Information and Computation, 237:204–214, 2014.
  * [17] Carla Groenland, Karolina Okrasa, Pawel Rzążewski, Alex Scott, Paul Seymour, and Sophie Spirkl.  $h$-colouring $p_{t}$-free graphs in subexponential time.  CoRR, 1803.05396, 2018.
  * [18] Martin Grötschel, László Lovász, and Alexander Schrijver.  Polynomial algorithms for perfect graphs.  Annals of Discrete Mathematics, 21:325–356, 1984.
  * [19] Andrzej Grzesik, Tereza Klimošová, Marcin Pilipczuk, and Michał Pilipczuk.  Polynomial-time algorithm for maximum weight independent set on $P_{6}$-free graphs.  CoRR, 1707.05491, 2017.
  * [20] Chính T. Hoàng, Marcin Kamiński, Vadim V. Lozin, Joe Sawada, and Xiao Shu.  Deciding $k$-colorability of $P_{5}$-free graphs in polynomial time.  Algorithmica, 57(1):74–81, 2010.
  * [21] Ian Holyer.  The NP-Completeness of edge-coloring.  SIAM J Comput, 10(4):718–720, 1981.
  * [22] Shenwei Huang.  Improved complexity results on $k$-coloring $P_{t}$-free graphs.  European Journal of Combinatorics, 51:336–346, 2016.
  * [23] Tommy R. Jensen and Bjarne Toft.  Graph coloring problems.  John Wiley & Sons, 1995.
  * [24] Daniel Král’, Jan Kratochvíl, Zsolt Tuza, and Gerhard J. Woeginger.  Complexity of coloring graphs without forbidden induced subgraphs.  Proc. WG 2001, LNCS, 2204:254–262, 2001.
  * [25] Jan Kratochvíl, Zsolt Tuza, and Margit Voigt.  New trends in the theory of graph colorings: choosability and list coloring.  Proc. DIMATIA-DIMACS Conference, 49:183–197, 1999.
  * [26] Van Bang Le, Bert Randerath, and Ingo Schiermeyer.  On the complexity of 4-coloring graphs without long induced paths.  TCS, 389(1-2):330–335, 2007.
  * [27] Daniel Leven and Zvi Galil.  NP completeness of finding the chromatic index of regular graphs.  Journal of Algorithms, 4(1):35–44, 1983.
  * [28] László Lovász.  Coverings and coloring of hypergraphs.  Congr. Numer., VIII:3–12, 1973.
  * [29] Daniël Paulusma.  Open problems on graph coloring for special graph classes.  Proc. WG 2015, LNCS, 9224:16–30, 2015.
  * [30] Bert Randerath and Ingo Schiermeyer.  3-colorability in P for p${}_{\mbox{6}}$-free graphs.  Discrete Applied Mathematics, 136(2-3):299–313, 2004.
  * [31] Bert Randerath and Ingo Schiermeyer.  Vertex colouring and forbidden subgraphs – a survey.  Graphs and Combinatorics, 20(1):1–40, 2004.
  * [32] Bert Randerath, Ingo Schiermeyer, and Meike Tewes.  Three-colourability and forbidden subgraphs. II: polynomial algorithms.  Discrete Mathematics, 251(1–3):137–153, 2002.
  * [33] Thomas J. Schaefer.  The complexity of satisfiability problems.  STOC, pages 216–226, 1978.
  * [34] Zsolt Tuza.  Graph colorings with local constraints - a survey.  Discussiones Mathematicae Graph Theory, 17(2):161–228, 1997.
  * [35] Gerhard J. Woeginger and Jiří Sgall.  The complexity of coloring graphs without long induced paths.  Acta Cybernetica, 15(1):107–117, 2001.