On Colouring (2P2 , H)-Free and (P5 , H)-Free Graphs⋆
Konrad K. Dabrowski and Daniël Paulusma

arXiv:1712.02447v1 [cs.CC] 6 Dec 2017

Department of Computer Science, Durham University,
Science Laboratories, South Road, Durham DH1 3LE, United Kingdom
{konrad.dabrowski,daniel.paulusma}@durham.ac.uk

Abstract. The Colouring problem asks whether the vertices of a graph can be coloured with at
most k colours for a given integer k in such a way that no two adjacent vertices receive the same colour.
A graph is (H1 , H2 )-free if it has no induced subgraph isomorphic to H1 or H2 . A connected graph H1
is almost classified if Colouring on (H1 , H2 )-free graphs is known to be polynomial-time solvable or
NP-complete for all but finitely many connected graphs H2 . We show that every connected graph H1
apart from the claw K1,3 and the 5-vertex path P5 is almost classified. We also prove a number of
new hardness results for Colouring on (2P2 , H)-free graphs. This enables us to list all graphs H for
which the complexity of Colouring is open on (2P2 , H)-free graphs and all graphs H for which the
complexity of Colouring is open on (P5 , H)-free graphs. In fact we show that these two lists coincide.
Moreover, we show that the complexities of Colouring for (2P2 , H)-free graphs and for (P5 , H)-free
graphs are the same for all known cases.

1

Introduction

Graph colouring is an extensively studied concept in both Computer Science and Mathematics due to its
many application areas. A k-colouring of a graph G = (V, E) is a mapping c : V → {1, . . . , k} such that
c(u) 6= c(v) whenever uv ∈ E. The Colouring problem that of deciding whether a given graph G has a
k-colouring for a given integer k. If k is fixed, then we write k-Colouring instead. It is well known that
even 3-Colouring is NP-complete [22].
Due to the computational hardness of Colouring, it is natural to restrict the input to special graph
classes. A class is hereditary if it closed under vertex deletion. Hereditary graph classes form a large collection
of well-known graph classes for which the Colouring problem has been extensively studied. A classical result
in the area is due to Grötschel, Lovász, and Schrijver [14], who showed that Colouring is polynomial-time
solvable for perfect graphs.
Graphs with no induced subgraph isomorphic to a graph in a set H are said to be H-free. It is readily
seen that a graph class G is hereditary if and only if it there exists a set H such that every graph in G is
H-free. If the graphs of H are required to be minimal under taking induced subgraphs, then H is unique.
For example, the set H of minimal forbidden induced subgraphs for the class of perfect graphs consists of
all odd holes and odd antiholes [6].
Král’, Kratochvíl, Tuza, and Woeginger [21] classified the complexity of Colouring for the case where H
consists of a single graph H. They proved that Colouring on H-free graphs is polynomial-time solvable
if H is an induced subgraph of P4 or P1 + P3 and NP-complete otherwise.1
Král’ et al. [21] also initiated a complexity study of Colouring for graph classes defined by two forbidden
induced subgraphs H1 and H2 . Such graph classes are said to be bigenic. For bigenic graph classes, no
dichotomy is known or even conjectured, despite many results [1,2,4,5,7,8,10,15,16,18,20,21,23,26,27,28,31].
For instance, if we forbid two graphs H1 and H2 with |V (H1 )| ≤ 4 and |V (H2 )| ≤ 4, then there are three
open cases left, namely when (H1 , H2 ) ∈ {(K1,3 , 4P1 ), (K1,3 , 2P1 + P2 ), (C4 , 4P1 )} (see [23] and Fig. 1). If H1
and H2 are connected with |V (H1 )| ≤ 5 and |V (H2 )| ≤ 5, then there are four open cases left, namely
when H1 = P5 and H2 ∈ {C3 + 2P1 , C3 + P2 , P1 + 2P2 } (see [20] and Fig. 2) and when H1 = K1,3 and
⋆
1

This paper was supported by EPSRC (EP/K025090/1) and the Leverhulme Trust (RPG-2016-258).
We refer to Section 2 for notation used throughout Section 1.

H2 = C4 + P1 (see [28] and Fig. 2). To give another example, Blanché et al. [1] determined the complexity of
Colouring for (H, H)-free graphs for every graph H except when H = P3 + sP1 for s ≥ 3 or H = P4 + sP1
for s ≥ 2.

K1,3

4P1

C4

2P1 + P2

Fig. 1. The graphs from the three pairs (H1 , H2 ) ∈ {(K1,3 , 4P1 ), (K1,3 , 2P1 + P2 ), (C4 , 4P1 )} of graphs on at most
four vertices, for which the complexity of Colouring on (H1 , H2 )-free graphs is still open.

K1,3

C4 + P1

C3 + 2P1

P5

C3 + P2

P1 + 2P2

Fig. 2. The graphs from the four pairs (H1 , H2 ) ∈ {(K1,3 , C4 + P1 ), (P5 , C3 + 2P1 ), (P5 , C3 + P2 ), (P5 , P1 + 2P2 )} of
connected graphs on at most five vertices, for which the complexity of Colouring on (H1 , H2 )-free graphs is still
open.

The related problems Precolouring Extension and List Colouring have also been studied for
bigenic graph classes. For the first problem, we are given a graph G, an integer k and a k-colouring c′ defined
on an induced subgraph of G. The question is whether G has a k-colouring c extending c′ . For the second
problem, each vertex u of the input graph G has a list L(u) of colours. Here the question is whether G has a
colouring c that respects L, that is, with c(u) ∈ L(u) for all u ∈ V (G). For the Precolouring Extension
problem no classification is known and we refer to the survey [12] for an overview on what is known. In
contrast to the incomplete classifications for Colouring and Precolouring Extension, Golovach and
Paulusma [13] showed a dichotomy for the complexity of List Colouring on bigenic graph classes.
Our Approach. To get a handle on the computational complexity classification of Colouring for bigenic
graph classes, we continue the line of research in [2,16,20,26,27,28] by considering pairs (H1 , H2 ), where H1
and H2 are both connected. We introduce the following notion. We say that a connected graph H1 is
almost classified if Colouring on (H1 , H2 )-free graphs is known to be either polynomial-time solvable or
NP-complete for all but finitely many connected graphs H2 . This leads to the following research question:
Which connected graphs are almost classified?
Our Results. In Section 3 we show, by combining known results from the literature, that every connected
graph H1 apart from the claw K1,3 and the 5-vertex path P5 is almost classified. In fact we show that the
number of pairs (H1 , H2 ) of connected graphs for which the complexity of Colouring is unknown is finite
if neither H1 nor H2 is isomorphic to K1,3 or P5 . In Section 4 we prove a number of new hardness results
for Colouring restricted to (2P2 , H2 )-free graphs (which form a subclass of (P5 , H2 )-free graphs). We do
the latter by adapting the NP-hardness construction from [11] for List Colouring restricted to complete
bipartite graphs. In Section 5, we first summarize our knowledge on the complexity of Colouring restricted
to (2P2 , H)-free graphs and (P5 , H)-free graphs. Afterwards, we list all graphs H for which the complexity of
2

Colouring on (2P2 , H)-free graphs is still open, and all graphs H for which the complexity of Colouring
on (P5 , H)-free graphs is still open. As it turns out, these two lists coincide. Moreover, the complexities of
Colouring for (2P2 , H)-free graphs and for (P5 , H)-free graphs turn out to be the same for all cases that
are known.

2

Preliminaries

We consider only finite, undirected graphs without multiple edges or self-loops. Let G = (V, E) be a graph.
The complement G of G is the graph with vertex set V (G) and an edge between two distinct vertices if and
only if these two vertices are not adjacent in G. For a subset S ⊆ V , we let G[S] denote the subgraph of G
induced by S, which has vertex set S and edge set {uv | u, v ∈ S, uv ∈ E}.
Let {H1 , . . . , Hp } be a set of graphs. A graph G is (H1 , . . . , Hp )-free if G has no induced subgraph
isomorphic to a graph in {H1 , . . . , Hp }. If p = 1, we may write H1 -free instead of (H1 )-free. The disjoint
union G + H of two vertex-disjoint graphs G and H is the graph (V (G) ∪ V (H), E(G) ∪ E(H)). The disjoint
union of r copies of a graph G is denoted by rG. A linear forest is the disjoint union of one or more paths.
The graphs Cr , Kr and Pr denote the cycle, complete graph and path on r vertices, respectively. The
graph K3 is also known as the triangle. The graph Kr,s denotes the complete bipartite graph with partition
classes of size r and s, respectively. The graph K1,3 is also called the claw.
The graph Sh,i,j , for 1 ≤ h ≤ i ≤ j, denotes the subdivided claw, that is, the tree that has only one
vertex x of degree 3 and exactly three leaves, which are of distance h, i and j from x, respectively. Observe
that S1,1,1 = K1,3 . The graph S1,1,2 is also known as the fork or the chair.
The graph Th,i,j with 0 ≤ h ≤ i ≤ j denotes the graph with vertices a0 , . . . , ah , b0 , . . . , bi and c0 , . . . , cj
and edges a0 b0 , b0 c0 , c0 a0 , ap ap+1 for p ∈ {0, . . . , h − 1}, bp bp+1 for p ∈ {0, . . . , i − 1} and cp cp+1 for
p ∈ {0, . . . , j − 1}. Note that T0,0,0 = C3 . The graph T0,0,1 = P1 + P3 is known as the paw, the graph T0,1,1
as the bull, the graph T1,1,1 as the net, and the graph T0,0,2 is known as the hammer; see also Fig. 3. Also
note that Th,i,j is the line graph of Sh+1,i+1,j+1 .

T0,0,0 = C3

T0,0,1 = paw

T0,1,1 = bull

T1,1,1 = net

T0,0,2 = hammer

Fig. 3. Examples of Th,i,j graphs.

Let T be the class of graphs every component of which is isomorphic to a graph Th,i,j for some 1 ≤
h ≤ i ≤ j or a path Pr for some r ≥ 1. The following result, which is due to Schindl and which we use in
Section 5, shows that the Th,i,j graphs play an important role for our study.
Theorem 1 ([31]). For p ≥ 1, let H1 , . . . , Hp be graphs whose complement is not in T . Then Colouring
is NP-complete for (H1 , . . . , Hp )-free graphs.

3

Almost Classified Graphs

In this section we prove the following result, from which it immediately follows that every connected graph
apart from K1,3 and P5 is almost classified. In Section 5 we discuss why K1,3 and P5 are not almost classified.
3

Theorem 2. There are only finitely many pairs (H1 , H2 ) of connected graphs with {H1 , H2 }∩{K1,3 , P5 } = ∅,
such that the complexity of Colouring on (H1 , H2 )-free graphs is unknown.
Proof. We first make a useful observation. Let H be a tree that is not isomorphic to K1,3 or P5 and that is
not an induced subgraph of P4 . If H contains a vertex of degree at least 4 then it contains an induced K1,4 .
If H has maximum degree 3, then since H is connected and not isomorphic to K1,3 , it must contain an
induced S1,1,2 . If H has maximum degree at most 2, then it is a path, and since it is not isomorphic to P5
and not an induced subgraph of P4 , it follows that H must be a path on at least six vertices. We conclude
that if H is a tree that is not isomorphic to K1,3 or P5 and that is not an induced subgraph of P4 , then H
contains K1,4 or S1,1,2 as an induced subgraph or H is a path on at least six vertices.
Now let (H1 , H2 ) be a pair of connected graphs with {H1 , H2 } ∩ {K1,3 , P5 } = ∅. If H1 or H2 is an induced
subgraph of P4 , then Colouring is polynomial-time solvable for (H1 , H2 )-free graphs, as Colouring is
polynomial-time solvable for P4 -free graphs (see, for example, [21]). Hence we may assume that this is not
the case. If H1 and H2 both contain at least one cycle [9] or both contain an induced K1,3 [17], then even
3-Colouring is NP-complete. Hence we may also assume that at least one of H1 , H2 is a tree and that at
least one of H1 , H2 is a K1,3 -free graph. This leads, without loss of generality, to the following two cases.
Case 1. H1 is a tree and K1,3 -free.
Then H1 is a path. First suppose that H1 has at least 22 vertices. It is known that 4-Colouring is NPcomplete for (P22 , C3 )-free graphs [19] and that Colouring is NP-complete for (P9 , C4 )-free graphs [10] and
for (2P2 , Cr )-free graphs for all r ≥ 5 [21]. Hence we may assume that H2 is a tree. By the observation at
the start of the proof, this implies that H2 contains an induced K1,4 , S1,1,2 or P6 . Therefore H contains
an induced 4P1 or 2P1 + P2 . Since H1 is a path on at least 22 vertices, H1 contains an induced 4P1 . As
Colouring is NP-complete for (4P1 , 2P1 +P2 )-free graphs [21], Colouring is NP-complete for (H1 , H2 )-free
graphs.
Now suppose that H1 has at most 21 vertices. By the observation at the start of the proof, H1 is a path
on at least six vertices. It is known that 5-Colouring is NP-complete for P6 -free graphs [18]. As K6 is
not 5-colourable, this means that 5-Colouring is NP-complete for (P6 , K6 )-free graphs, as observed in [12].
Therefore we may assume that H2 is K6 -free. Recall that Colouring is NP-complete for (2P1 + P2 , 4P1 )-free
graphs [21], which are contained in the class of (P6 , 4P1 )-free graphs. Therefore we may assume that H2 is
4P1 -free. Since H2 is (K6 , 4P1 )-free, Ramsey’s Theorem [29] implies that |V (H2 )| is bounded by a constant.
We conclude that both H1 and H2 have size bounded by a constant.
Case 2. H1 is a tree and not K1,3 -free, and H2 is K1,3 -free and not a tree.
Then H1 contains a vertex of degree at least 3 and H2 contains an induced cycle Cr for some r ≥ 3. It
is known that 3-Colouring is NP-complete for (K1,5 , C3 )-free graphs [25] and for (K1,3 , Cr )-free graphs
whenever r ≥ 4 [21]. We may therefore assume that H1 is a tree of maximum degree at most 4 and that H2
contains at least one induced C3 but no induced cycles on more than three vertices. Recall that 4-Colouring
is NP-complete for (P22 , C3 )-free graphs [19]. Hence we may assume that H1 is a P22 -free tree. As H1 has
maximum degree at most 4, we find that H1 has a bounded number of vertices.
By assumption, H1 contains a vertex of degree at least 3. As Colouring is NP-complete for (K1,3 , K4 )free graphs [21], we may assume that H2 is K4 -free. By the observation at the start of the proof, H1 must
contain an induced K1,4 or S1,1,2 . Recall that Colouring is NP-complete for the class of (2P1 + P2 , 4P1 )-free
graphs [21], which is contained in the class of (K1,4 , S1,1,2 , 4P1 )-free graphs. Hence we may assume that H2 is
4P1 -free. Since H2 is (K4 , 4P1 )-free, Ramsey’s Theorem [29] implies that |V (H2 )| is bounded by a constant.
Again, we conclude that in this case both H1 and H2 have size bounded by a constant.
⊓
⊔
Corollary 1. Every connected graph apart from K1,3 and P5 is almost classified.

4

Hardness Results

In this section we prove that Colouring restricted to (2P2 , H)-free graphs is NP-complete for several
graphs H. To prove our results we adapt a hardness construction from Golovach and Heggernes [11] for
4

proving that List Colouring is NP-complete for complete bipartite graphs. As observed in [13], a minor
modification of this construction yields that List Colouring is NP-complete for complete split graphs,
which are the graphs obtained from complete bipartite graphs by changing one of the bipartition classes into
a clique.
We first describe the construction of [11], which uses a reduction from the NP-complete [30] problem NotAll-Equal 3-Satisfiability with positive literals only. To define this problem, let X = {x1 , x2 , . . . , xn }
be a set of logical variables, and let C = {C1 , C2 , . . . , Cm } be a set of 3-literal clauses over X in which all
literals are positive and every literal appears at most once in each clause. The question is whether X has a
truth assignment such that each clause in C contains at least one true literal and at least one false literal. If
so, we say that such a truth assignment is satisfying.
Let (X, C) be an instance of Not-All-Equal 3-Satisfiability with positive literals only. We construct
an instance (G1 , L) of List Colouring as follows. For each xi we introduce a vertex, which we also denote
by xi and which we say is of x-type. We define L(x1 ) = {1, 2}, L(x2 ) = {3, 4}, . . . , L(xn ) = {2n − 1, 2n}.
In this way, each xi has one odd colour and one even colour in its list, and all lists L(xi ) are pairwise
disjoint. For each Cj we introduce two vertices, which we denote by Cj and Cj′ and which we say are of
C-type. If Cj = {xg , xh , xi } with L(xg ) = {a, a + 1}, L(xh ) = {b, b + 1} and L(xi ) = {c, c + 1}, then we set
L(Cj ) = {a, b, c} and L(Cj′ ) = {a + 1, b + 1, c + 1}. Hence each Cj has only odd colours in its list and each Cj′
has only even colours in its list. To obtain the graph G1 we add an edge between every vertex of x-type and
every vertex of C-type. Note that G1 is a complete bipartite graph with bipartition classes {x1 , . . . , xn } and
′
{C1 , . . . , Cm } ∪ {C1′ , . . . , Cm
}.
We also construct an instance (G2 , L) where G2 is obtained from G1 by adding edges between every pair
of vertices of x-type. Note that G2 is a complete split graph.
The following lemma is straightforward. We refer to [11] for a proof for the case involving G1 . The case
involving G2 follows from this proof and the fact that the lists L(xi ) are pairwise disjoint, as observed in [13].
Lemma 1 ([11]). (C, X) has a satisfying truth assignment if and only if G1 has a colouring that respects L
if and only if G2 has a colouring that respects L.
We now extend G1 and G2 into graphs G′1 and G′2 , respectively, by adding a clique K consisting of 2n
new vertices k1 , . . . , k2n and by adding an edge between a vertex kℓ and a vertex u of the original graph if
and only if ℓ ∈
/ L(u). We say that the vertices k1 , . . . , k2n are of k-type.
Lemma 2. (C, X) has a satisfying truth assignment if and only if G′1 has a 2n-colouring if and only if G′2
has a 2n-colouring.
Proof. Let i ∈ {1, 2}. By Lemma 1, we only need to show that Gi has a colouring that respects L if and
only if G′i has a 2n-colouring. First suppose that Gi has a colouring c that respects L. We extend c to a
colouring c′ of G′i by setting c′ (kℓ ) = ℓ for ℓ ∈ {1, . . . , 2n}. Now suppose that G′i has a 2n-colouring c′ . As the
k-type vertices form a clique, we may assume without loss of generality that c′ (kℓ ) = ℓ for ℓ ∈ {1, . . . , 2n}.
Hence the restriction of c′ to Gi yields a colouring c that respects L.
⊓
⊔
In the next two lemmas we show forbidden induced subgraphs in G′1 and G′2 , respectively. The complements of these forbidden graphs are shown in Figs. 4 and 5, respectively.

2P2 = C4

3P2

T0,2,2

Fig. 4. Graphs that are not induced subgraphs of the complement of G′1 .

5

Lemma 3. The graph G′1 is (2P2 , 3P2 , T0,2,2 )-free.
Proof. We will prove that G′1 is (C4 , 3P2 , T0,2,2 )-free. Observe that in G′1 , the set of x-type vertices is a clique,
the set of C-type vertices is a clique and the set of k-type vertices is an independent set. Furthermore, in G′1 ,
no x-type vertex is adjacent to a C-type vertex.
C4 -freeness. For contradiction, suppose that G′1 contains an induced subgraph H isomorphic to C4 ; say the
vertices of H are u1 , u2 , u3 , u4 in that order. As the union of the set of x-type and C-type vertices induces a
P3 -free graph in G′1 , there must be at least two vertices of the C4 that are neither x-type nor C-type. Since
the k-type vertices form an independent set, we may assume without loss of generality that u1 and u3 are
of k-type. It follows that u2 and u4 cannot be of k-type. As the set of x-type vertices and the set of C-type
vertices each from a clique in G′1 , but u2 is non-adjacent to u4 , we may assume without loss of generality
that u2 is of x-type and u4 is of C-type. Then u4 is adjacent to the two k-type neighbours of an x-type
vertex, which correspond to an even and odd colour. This is not possible as u4 , being a C-type vertex, is
adjacent in G′1 to (exactly three) k-type vertices, which correspond either to even colours only or to odd
colours only. We conclude that G′1 is C4 -free.
3P2 -freeness. For contradiction, suppose that G′1 contains an induced subgraph H isomorphic to 3P2 . As
the C-type vertices and x-type vertices each form a clique in G′1 , one edge of H must consist of two k-type
vertices. This is not possible, as k-type vertices form an independent set in G′1 . We conclude that G′1 is
3P2 -free.
T0,2,2 -freeness. For contradiction, suppose that G′1 contains an induced subgraph H isomorphic to T0,2,2
with vertices a0 , a1 , a2 , b0 , b1 , b2 , c0 and edges a0 b0 , b0 c0 , c0 a0 , a0 a1 , a1 a2 , b0 b1 , b1 b2 . As the k-type vertices
form an independent set in G′1 , at least one of a1 , a2 and at least one of b1 , b2 is of x-type or C-type. As
the x-type vertices and the C-type vertices form cliques in G′1 , we may assume without loss of generality
that at least one of a1 , a2 is of C-type and at least one of b1 , b2 is of x-type. As the C-type vertices and
the x-type vertices each form a clique in G′1 , this means that c0 must be of k-type, a0 cannot be of x-type
and b0 cannot be of C-type. As k-type vertices form an independent set in G′1 , a0 and b0 cannot be of k-type.
Therefore a0 is of C-type and b0 is of x-type. This is a contradiction, as C-type vertices are non-adjacent to
⊓
⊔
x-type vertices. We conclude that G′1 is T0,2,2 -free.

2P2 = C4

2C3 = K3,3

C3 + P4

2P4

T0,0,4

Fig. 5. Graphs that are not induced subgraphs of the complement of G′2 .

Lemma 4. The graph G′2 is (2P2 , 2C3 , C3 + P4 , 2P4 , T0,0,4 )-free.
Proof. We will prove that G′2 is (C4 , 2C3 , C3 + P4 , 2P4 , T0,0,4 )-free. Observe that in G′2 , the set of C-type
vertices is a clique, the set of x-type vertices is an independent set and the set of k-type vertices is an
independent set. Furthermore, in G′2 , no x-type vertex is adjacent to a C-type vertex and every x-type
vertex has degree 2. In fact, the union of the set of x-type vertices and the k-type vertices induces a disjoint
union of P3 s in G′2 .
C4 -freeness. For contradiction, suppose that G′2 contains an induced subgraph H isomorphic to C4 , say the
vertices of H are u1 , u2 , u3 , u4 in that order. As the union of the set of x-type and C-type vertices induces a
P3 -free graph in G′2 , there must be at least two vertices of the C4 that are neither x-type nor C-type. Since
6

the k-type vertices form an independent set, we may assume without loss of generality that u1 and u3 are of
k-type. It follows that u2 and u4 cannot be of k-type. As the set of vertices of C-type form a clique in G′2 ,
at least one of u2 , u4 , say u2 , is of x-type. If u4 is also of x-type, then u2 and u4 are x-type vertices with the
same two colours in their list, namely those corresponding to u1 and u3 . This is not possible. Thus u4 must
be of C-type. Then u4 is adjacent to the two k-type neighbours of an x-type vertex, which correspond to an
even and odd colour. This is not possible as u4 , being a C-type vertex, is adjacent in G′2 to (exactly three)
k-type vertices, which correspond either to even colours only or to odd colours only. We conclude that G′2 is
C4 -free.
(2C3 , C3 + P4 , 2P4 )-freeness. For contradiction, suppose that G′2 contains an induced subgraph H isomorphic to 2C3 , C3 + P4 or 2P4 . As the k-type and x-type vertices induce a disjoint union of P3 s in G′2 , both
components of H must contain a C-type vertex. This is not possible, as C-type vertices form a clique in G′2 .
We conclude that G′2 is (2C3 , C3 + P4 , 2P4 )-free.
T0,0,4 -freeness. For contradiction, suppose that G′2 contains an induced subgraph H isomorphic to T0,0,4
with vertices a0 , a1 , a2 , a3 , a4 , b0 , c0 and edges a0 b0 , b0 c0 , c0 a0 , a0 a1 , a1 a2 , a2 a3 , a3 a4 .
First suppose, that neither b0 nor c0 is of C-type. Since the union of the set of x-type vertices and the
k-type vertices induces a disjoint union of P3 s in G′2 it follows that a0 is of C-type. Since b0 and c0 are not of
C-type and no vertex of C-type has a neighbour of x-type in G′2 , it follows that b0 and c0 must be of k-type.
This is not possible, because the k-type vertices form an independent set in G′2 .
Now suppose that at least one of b0 , c0 is of C-type. Since the vertices of C-type induce a clique in G′2 , it
follows that no vertex in A := {a1 , a2 , a3 , a4 } is of C-type. Since A induces a P4 in G′2 , but the union of the
set of x-type vertices and the k-type vertices induces a disjoint union of P3 s in G′2 , this is a contradiction.
We conclude that G′2 is T0,0,4 -free.
⊓
⊔
We are now ready to state the two main results of this section. It is readily seen that Colouring belongs
to NP. Then the first theorem follows from Lemma 2 combined with Lemma 3, whereas the second one follows
from Lemma 2 combined with Lemma 4. Note that 2C3 is isomorphic to K3,3 .
Theorem 3. Colouring is NP-complete for (2P2 , 3P2 , T0,2,2 )-free graphs.
Theorem 4. Colouring is NP-complete for (2P2 , 2C3 , C3 + P4 , 2P4 , T0,0,4 )-free graphs.

5

Conclusions

We showed that every connected graph is almost classified except for the claw and the P5 . Our notion of
almost classified graphs originated from recent work [16,20,27,28] on Colouring for (H1 , H2 )-free graphs
for connected graphs H1 and H2 , in particular when H1 = P5 . We decreased the number of open cases for
the latter graph by showing new NP-hardness results for (2P2 , H)-free graphs. In the following theorem we
summarize all known results for Colouring restricted to (2P2 , H)-free graphs and (P5 , H)-free graphs.
Theorem 5. Let H be a graph on n vertices. Then the following two statements hold:
(i) If H contains a graph in {C3 + P4 , 3P2 , 2P4 } as an induced subgraph, or H is not an induced subgraph
of T1,1,3 + P2n−1 , then Colouring is NP-complete for (2P2 , H)-free graphs.
(ii) If H is an induced subgraph of a graph in {2P1 + P3 , P1 + P4 , P2 + P3 , P5 , T0,0,1 + P1 , T0,1,1 , T0,0,2 } or of
sP1 + P2 for some integer s ≥ 0, then Colouring is polynomial-time solvable for (P5 , H)-free graphs.
Proof. If H contains a graph in {2C3 , C3 + P4 , 3P2 , 2P4 , T0,2,2 , T0,0,4 } as an induced subgraph, then Colouring is NP-complete for (2P2 , H)-free graphs due to Theorems 3 and 4. We may therefore assume that H is
(2C3 , C3 + P4 , 3P2 , 2P4 , T0,2,2 , T0,0,4 )-free. (Note that T1,1,3 + P2n−1 is (2C3 , T0,2,2 , T0,0,4 )-free.)
Recall that T is the class of graphs every component of which is isomorphic to a graph Th,i,j for some
/ T . Therefore, if H ∈
/ T , then Colouring
1 ≤ h ≤ i ≤ j or a path Pr for some r ≥ 1. Note that 2P2 = C4 ∈
is NP-complete for (2P2 , H)-free graphs by Theorem 1. We may therefore assume that H ∈ T . Since H is
7

2C3 -free, H can contain at most one component that is not a path. Since H is (T0,2,2 , T0,0,4 )-free, if H does
have a component that is not a path, then this component must be an induced subgraph of T1,1,3 . The union
of components of H that are isomorphic to paths form an induced subgraph of P2n−1 . Therefore H is an
induced subgraph of T1,1,3 + P2n−1 .
It is known that Colouring is polynomial-time solvable for (P5 , H)-free graphs if H is an induced
subgraph of 2P1 + P3 [27], P1 + P4 (this follows from the fact that (P5 , P1 + P4 )-free graphs have cliquewidth at most 5 [3]; see also [2] for a linear-time algorithm), P2 + P3 [28], P5 [16], T0,0,1 + P1 [20], T0,1,1 [20],
T0,0,2 [20] or sP1 + P2 for some integer s ≥ 0 [28].
⊓
⊔
Theorem 5 leads to the following open problem, which shows how the P5 is not almost classified. Recall
that T0,0,0 = C3 .
Open Problem 1 Determine the complexity of Colouring for (2P2 , H)-free graphs and for (P5 , H)-free
graphs if
–
–
–
–
–
–

H
H
H
H
H
H

= sP1 + Pt + Th,i,j for 0 ≤ h ≤ i ≤ j ≤ 1, s ≥ 0 and 2 ≤ t ≤ 3
= sP1 + Th,i,j for 0 ≤ h ≤ i ≤ 1 ≤ j ≤ 3 and s ≥ 0 such that h + i + j + s ≥ 3
= sP1 + T0,0,0 for s ≥ 2
= sP1 + Pt for s ≥ 0 and 3 ≤ t ≤ 7 such that s + t ≥ 6
= sP1 + Pt + Pu for s ≥ 0, 2 ≤ t ≤ 3 and 3 ≤ u ≤ 4 such that s + t + u ≥ 6
= sP1 + 2P2 for s ≥ 1.

Open Problem 1 shows the following.
– The open cases for Colouring restricted to (2P2 , H)-free graphs and (P5 , H)-free graphs coincide.
– The graph H in each of the open cases is connected.
– The number of minimal open cases is 10, namely when H ∈ {C3 + 2P1 , C3 + P2 , P1 + 2P2 } (see also
Section 1) and when H ∈ {3P1 + P3 , 2P1 + P4 , 2P3 , P6 , T0,1,1 + P1 , T0,1,2 , T1,1,1 }.
As every graph H listed in Open Problem 1 appears as an induced subgraph in both the graph G′1 and the
graph G′2 defined in Section 4, we need new arguments to solve the open cases in Problem 1.
The complexity of Colouring for (K1,3 , H)-free graphs is less clear. As mentioned in Section 1, the
cases where H ∈ {4P1 , 2P1 + P2 , C4 + P1 } are still open. Moreover, K1,3 is not almost classified, as the case
H = Pt is open for all t ≥ 6 (polynomial-time solvability for t = 5 was shown in [26]). Note that |E(H)| may
be arbitrarily large, while Open Problem 1 shows that |E(H)| ≤ 8 in all open cases for the P5 . Since we have
no new results for the case H1 = K1,3 , we refer to [24] for further details or to the summary of Colouring
restricted to (H1 , H2 )-free graphs in [12].

References
1. A. Blanché, K. K. Dabrowski, M. Johnson, and D. Paulusma. Hereditary graph classes: When the complexities
of Colouring and Clique Cover coincide. CoRR, abs/1607.06757, 2016.
2. H. L. Bodlaender, A. Brandstädt, D. Kratsch, M. Rao, and J. Spinrad. On algorithms for (P5 ,gem)-free graphs.
Theoretical Computer Science, 349(1):2–21, 2005.
3. A. Brandstädt, H.-O. Le, and R. Mosca. Chordal co-gem-free and (P5 ,gem)-free graphs have bounded clique-width.
Discrete Applied Mathematics, 145(2):232–241, 2005.
4. H. Broersma, P. A. Golovach, D. Paulusma, and J. Song. Determining the chromatic number of triangle-free
2P3 -free graphs in polynomial time. Theoretical Computer Science, 423:1–10, 2012.
5. K. Cameron and C. T. Hoàng. Solving the clique cover problem on (bull,C4 )-free graphs. CoRR, abs/1704.00316,
2017.
6. M. Chudnovsky, N. Robertson, P. Seymour, and R. Thomas. The strong perfect graph theorem. Annals of
Mathematics, 164(1):51–229, 2006.
7. K. K. Dabrowski, F. Dross, and D. Paulusma. Colouring diamond-free graphs. Journal of Computer and System
Sciences, 89:410–431, 2017.

8

8. K. K. Dabrowski, P. A. Golovach, and D. Paulusma. Colouring of graphs with Ramsey-type forbidden subgraphs.
Theoretical Computer Science, 522:34–43, 2014.
9. T. Emden-Weinert, S. Hougardy, and B. Kreuter. Uniquely colourable graphs and the hardness of colouring
graphs of large girth. Combinatorics, Probability and Computing, 7(04):375–386, 1998.
10. S. Gaspers, S. Huang, and D. Paulusma. Colouring square-free graphs without long induced paths. Manuscript,
2017.
11. P. A. Golovach and P. Heggernes. Choosability of P5 -free graphs. Proc. MFCS 2009, LNCS, 5734:382–391, 2009.
12. P. A. Golovach, M. Johnson, D. Paulusma, and J. Song. A survey on the computational complexity of colouring
graphs with forbidden subgraphs. Journal of Graph Theory, 84(4):331–363, 2017.
13. P. A. Golovach and D. Paulusma. List coloring in the absence of two subgraphs. Discrete Applied Mathematics,
166:123–130, 2014.
14. M. Grötschel, L. Lovász, and A. Schrijver. Polynomial algorithms for perfect graphs. Annals of Discrete Mathematics, 21:325–356, 1984.
15. P. Hell and S. Huang. Complexity of coloring graphs without paths and cycles. Discrete Applied Mathematics,
216, Part 1:211–232, 2017.
16. C. T. Hoàng and D. A. Lazzarato. Polynomial-time algorithms for minimum weighted colorings of (P5 , P5 )-free
graphs and similar graph classes. Discrete Applied Mathematics, 186:106–111, 2015.
17. I. Holyer. The NP-Completeness of edge-coloring. SIAM Journal on Computing, 10(4):718–720, 1981.
18. S. Huang. Improved complexity results on k-coloring Pt -free graphs. European Journal of Combinatorics, 51:336–
346, 2016.
19. S. Huang, M. Johnson, and D. Paulusma. Narrowing the complexity gap for colouring (Cs , Pt )-free graphs. The
Computer Journal, 58(11):3074–3088, 2015.
20. T. Karthick, F. Maffray, and L. Pastor. Polynomial cases for the vertex coloring problem. CoRR, abs/1709.07712,
2017.
21. D. Král’, J. Kratochvíl, Zs. Tuza, and G. J. Woeginger. Complexity of coloring graphs without forbidden induced
subgraphs. Proc. WG 2001, LNCS, 2204:254–262, 2001.
22. L. Lovász. Coverings and coloring of hypergraphs. Congressus Numerantium, VIII:3–12, 1973.
23. V. V. Lozin and D. S. Malyshev. Vertex coloring of graphs with few obstructions. Discrete Applied Mathematics,
216, Part 1:273–280, 2017.
24. V. V. Lozin and C. Purcell. Coloring vertices of claw-free graphs in three colors. Journal of Combinatorial
Optimization, 28(2):462–479, 2014.
25. F. Maffray and M. Preissmann. On the NP-completeness of the k-colorability problem for triangle-free graphs.
Discrete Mathematics, 162(1–3):313–317, 1996.
26. D. S. Malyshev. The coloring problem for classes with two small obstructions. Optimization Letters, 8(8):2261–
2270, 2014.
27. D. S. Malyshev. Two cases of polynomial-time solvability for the coloring problem. Journal of Combinatorial
Optimization, 31(2):833–845, 2016.
28. D. S. Malyshev and O. O. Lobanova. Two complexity results for the vertex coloring problem. Discrete Applied
Mathematics, 219:158–166, 2017.
29. F. P. Ramsey. On a problem of formal logic. Proceedings of the London Mathematical Society, s2-30(1):264–286,
1930.
30. T. J. Schaefer. The complexity of satisfiability problems. Proc. STOC 1978, pages 216–226, 1978.
31. D. Schindl. Some new hereditary classes where graph coloring remains NP-hard. Discrete Mathematics, 295(1–
3):197–202, 2005.

9

