Polynomial Cases for the Vertex Coloring Problem

arXiv:1709.07712v1 [math.CO] 22 Sep 2017

T. Karthick

∗

Frédéric Maffray†

Lucas Pastor‡

September 25, 2017

Abstract
The computational complexity of the Vertex Coloring problem is known for all hereditary classes
of graphs defined by forbidding two connected five-vertex induced subgraphs, except for seven cases.
We prove the polynomial-time solvability of four of these problems: for (P5 , dart)-free graphs, (P5 ,
banner)-free graphs, (P5 , bull)-free graphs, and (fork, bull)-free graphs.

Keywords. Graph algorithms; Vertex coloring; Two forbidden induced subgraphs; P5 -free graphs.

1

Introduction

Vertex coloring of graphs is one among the basic graph colorings and has a long history starting with
the four color problem, and is widely studied in graph theory and in theoretical computer science. It
occupies a central place in the complexity theory of algorithms and arises naturally in many real world
applications such as storage problem, register allocation and time table scheduling. Recent publications
show that vertex coloring problems still receive maximum attention.
A vertex coloring (or simply coloring) of a graph G is an assignment of colors to the vertices of G
such that no two adjacent vertices receive the same color. That is, a partitioning of the vertex set of G
into stable sets (called color classes), where a stable set is a set of pairwise nonadjacent vertices. The
minimum number of colors required to color G is called the chromatic number of G, and is denoted by
χ(G). Given a graph G, the Minimum Vertex Coloring (VC) problem is to determine the chromatic
number χ(G). The VC problem is well-known to be N P -complete in general, see [13], and also in may
restricted classes of graphs. Lund and Yannakakis [23] showed that there exists a constant ǫ > 0 such
that approximating the chromatic number of an arbitrary graph within a factor of nǫ is N P -hard, where
n is the number of vertices. This result is further improved by Feige and Kilian [12], who proved that the
chromatic number cannot be approximated within a factor of n1−ǫ , for any ǫ > 0, unless N P 6= ZP P .
These algorithmic issues are main motivations for current research to study the VC problem in restricted
classes of graphs.
A class of graphs X is hereditary if every induced subgraph of a member of X is also in X . If F is
a family of graphs, a graph G is said to be F -free if it contains no induced subgraph isomorphic to any
graph in F . In this paper, we are interested in the VC problem for some hereditary classes of graphs which
are defined by forbidden induced subgraphs. The VC problem remains N P -complete even for restricted
classes of graphs, such as triangle-free graphs [25], P6 -free graphs [18], and K1,3 -free graphs (see [22]).
∗ Computer

Science Unit, Indian Statistical Institute, Chennai Centre, Chennai 600029, India.
Laboratoire G-SCOP, Univ. Grenoble, France.
‡ Laboratoire G-SCOP, Univ. Grenoble, France.
† CNRS,

1

Dart

Co-dart

Banner

Bull

Fork

Hammer

Figure 1: Some special graphs.
But, for many classes of graphs, such as perfect graphs [15] and for (2P3 , triangle)-free graphs [3], the
VC problem can be solved in polynomial time. The VC problem for P5 -free graphs is N P -complete [21],
but for every fixed k, the problem of coloring a P5 -free graph with k colors admits a polynomial-time
algorithm [16]. Král et al. [21] showed that the VC problem is solvable in polynomial time for H-free
graphs, whenever H is a (not necessarily proper) induced subgraph of P4 or P3 + K1 ; otherwise, the
problem is N P -complete. When we forbid two induced subgraphs, only partial results are known for the
VC problem. The motivation of this paper is the following open problem of Golovach et al. [14].
Problem 1.1 ([14]) Complete the classification of the complexity of the Vertex Coloring problem
for (G1 , G2 )-free graphs.
We refer to [14] for a recent comprehensive survey and for other open problems on the computational complexity of the VC problem for classes of graphs defined by forbidden induced subgraphs, and
we refer to Theorem 1 of [27], for the complexity dichotomy of the VC problem for some classes of
graphs which are defined by two forbidden induced subgraphs. It is known that the VC problem is either
N P -complete or polynomial time solvable for the classes of graphs which are defined by two four-vertex
forbidden induced subgraphs, except for three classes of graphs namely, (O4 , C4 )-free graphs, (K1,3 , O4 )free graphs, and for (K1,3 , K2 + O2 )-free graphs. Recently, the complexity dichotomy of the VC problem
for classes of graphs which are defined by two connected five-vertex forbidden induced subgraphs received considerable attention. The VC problem is known to be solvable in polynomial time for: (P5 ,
gem)-free graphs [1], (P5 , P5 )-free graphs [17], (P5 , P3 + O2 )-free graphs [26], (P5 , P3 + P2 )-free graphs
[27], and for (P5 , K5 − e)-free graphs [27]. In particular, the complexity dichotomy of the VC problem is known for classes of graphs which are defined by two connected five-vertex forbidden induced
subgraphs except for the following seven cases: (fork, bull)-free graphs, and (P5 , H)-free graphs, where
H ∈ {K3 + O2 , K2,3 , dart, banner, bull, 4-wheel}.
In the weighted version of the problem, we are given a graph and an integer weight function w on
V (G), and the Minimum Weighted Vertex Coloring (WVC) problem is to find k not necessarily
different stable sets S1 , S2 , . . . , Sk such that every vertex x belongs to at least w(x) of these sets. The
smallest such k is denoted by χw (G) and is called the weighted chromatic number of G; the stable sets
Si are called a weighted coloring of G. Note that in the context of the WVC problem, the size of the
P
input is considered to be |V (G)| + |E(G)| + x∈V (G) w(x). Hence, algorithms for weighted graphs are
polynomial on the sum of weights but not necessarily on the number of vertices. However, whenever we
want to solve the (unweighted) coloring problem on a graph G and we reduce it to a weighted problem
on an another graph, it will always be the case that the size of the reduced instance is not larger than
|V (G)| + |E(G)| (as can be easily checked, since the reduction usually consists in replacing a subset X of
vertices with one vertex of weight at most |X|); hence the final complexity will be polynomial in |V (G)|.
In this paper, using decomposition techniques, we establish structure theorems and derive the polynomial time solvability of the WVC problem for the following classes (see Figure 1), which are four of
2

the seven open cases mentioned above:
• (P5 , dart)-free graphs,
• (P5 , banner)-free graphs,
• (P5 , bull)-free graphs,
• (fork, bull)-free graphs.
Rao [29] showed that the VC problem is polynomial-time solvable for graphs of bounded cliquewidth. Note that the clique width is unbounded for each of the four classes above. This is because each
class contains the class of co-triangle-free graphs, and it is well-known that that class has unbounded
cliquewidth.

2

Notations and preliminaries

For notations and terminology which are not defined here, we follow [2]. All our graphs are finite, simple
and undirected. For any integer k, we write [k] to denote the set {1, 2, . . . , k}. Let Kn , Pn , Cn and On
denote respectively the complete graph, the chordless path, the chordless cycle, and the edgeless graph on
n vertices. The graph K3 is usually called a triangle. A triad in a graph G is a subset of three mutually
non-adjacent vertices.
Given two vertex-disjoint graphs G1 and G2 , the graph G1 + G2 is the graph with V (G1 + G2 )
= V (G1 ) ∪ V (G2 ) and E(G1 + G2 ) = E(G1 ) ∪ E(G2 ). For any positive integer k, kG denotes the union
of k graphs each isomorphic to G. For a graph G, the complement of G is denoted by G. The graph P5
is usually called the house. The complement of a dart is called a co-dart. See Figure 1 for some of the
special graphs used in this paper.
Let G be a graph. For S ⊆ V (G) we denote by G[S] the induced subgraph of G with vertex-set S,
and we simply write [S] instead of G[S]. If H is an induced subgraph of G, then we write H ⊑ G. For
a vertex v ∈ V (G), the neighborhood N (v) of v is the set {u ∈ V (G) | uv ∈ E(G)}. Given a subset
S ⊆ V (G) and v ∈ V (G) \ S, let NS (v) denote the set N (v) ∩ S.
For v ∈ V (G) and S ⊆ V (G), we say that a vertex v is complete to S if v is adjacent to every vertex
in S, and that v is anticomplete to S if v has no neighbor in S. For two sets S, T ⊆ V (G) we say that S
is complete to T if every vertex of S is adjacent to every vertex of T , and we say that S is anticomplete
to T if no vertex of S is adjacent to any vertex of T .
A clique in a graph G is a subset of pairwise adjacent vertices in G. A clique cover of a graph G is a
partition of V (G) into cliques. Hence of a coloring of a graph G is a clique cover of G and vice-versa.
A hole is a chordless cycle Ck , where k ≥ 5, and an anti-hole is the complement of a hole. A hole or
an anti-hole is odd if k is odd. A graph G is perfect if χ(H) = ω(H), for every induced subgraph H of
G, where ω(H) is the maximum number of vertices that are mutually adjacent in H. The Strong Perfect
Graph Theorem (SPGT) [6] states that a graph G is perfect if and only if it does not contain an odd-hole
or an odd anti-hole.
A clique separator/clique cutset in a connected graph G is a subset Q of vertices in G such that Q is
a clique and such that the graph induced by V (G) \ Q is disconnected. For a given graph G, a C-block
is a maximal induced subgraph of G without proper clique separators. For a class of graphs X , let [X ]C
denotes the set of all graphs whose every C-block belongs to X .

3

Theorem 2.1 ([27]) If the WVC problem can be solved in polynomial time for a hereditary class X ,
then it is so for [X ]C .

A homogeneous set in a graph G is a set S ⊆ V (G) such that every vertex in V (G) \ S is either
complete or anticomplete to S. A homogeneous set is proper if it contains at least two vertices and is
different from V (G). A module is a homogeneous set M such that every homogeneous set S satisfies
either S ⊆ M or M ⊆ S or S ∩ M = ∅. In particular V (G) is a module and every one-vertex set is a
module. The trivial modules in G are V (G), ∅, and all one-elementary vertex sets. A graph G is prime
if it contains only trivial modules. Note that prime graphs with at least three vertices are connected. It
follows from their definition that the modules form a “nested” family, so their inclusion relation can be
represented by a tree, and any graph G has at most 2|V (G)| − 1 modules. The modules of a graph G can
be produced by an algorithm of linear (i.e., O(|V (G)| + |E(G)|)) time complexity [9, 10, 28]. For a class
of graphs X , let [X ]P denotes the set of all graphs whose every prime induced subgraph belongs to X .
Theorem 2.2 ([27], see also [17]) If the WVC problem can be solved in polynomial time for a hereditary class X , then it is so for [X ]P .


3

WVC for (P5 , dart)-free graphs

We start with the following lemmas.
a1

a4

a1

a4

b1

a1
b2

a2
a3

b1 a2

a1 b2

b2

b1

a2

a2

b1
b2

a1

b1
b2

a3
a2

a4

a3

a4

a3

H1

H2

H3

H4

b4

b3

H5

Figure 2: Special graphs used in Lemma 3.1 and Lemma 3.2.

Lemma 3.1 Let G be a prime dart-free graph. Then G is (H1 , H2 )-free.
Proof of Lemma 3.1. Suppose to the contrary that G contains an induced subgraph which is isomorphic
to Hi , for i ∈ {1, 2} (as shown in Figure 2). Since G is prime, {a1 , a2 } is not a module, so there exists
a vertex x ∈ V \ V (Hi ) such that (up to symmetry) xa1 ∈ E and xa2 ∈
/ E. Then since {x, a1 , b1 , b2 , a2 }
does not induce a dart, x has a neighbor in {b1 , b2 }. By symmetry, we may assume that xb1 ∈ E. Then
since {x, a1 , a2 , b1 , a3 } does not induce a dart, xa3 ∈ E.
Now, suppose that i = 1. Then since {x, a1 , a2 , b1 , a4 } does not induce a dart, xa4 ∈ E. But, then
{a4 , x, a3 , b1 , a2 } induces a dart. So, G is H1 -free.
So, suppose that i = 2. Then since {b2 , a2 , a4 , a1 , x} and {b1 , x, a4 , a1 , b2 } do not induce a dart, we have
xb2 ∈ E. But, then {b1 , x, b2 , a1 , a4 } or {b1 , a3 , b2 , x, a4 } induces a dart. So, G is H2 -free.
This shows Lemma 3.1.

Lemma 3.2 Let G be a prime (P5 , dart)-free graph. Then G is (H3 , H4 , H5 )-free.

4

Proof of Lemma 3.2. Suppose to the contrary that G contains an induced subgraph which is isomorphic
to Hi , for i ∈ {3, 4, 5} (as shown in Figure 2). Since G is prime, {a1 , a2 } is not a module, so there exists
a vertex x ∈ V \ V (Hi ) such that (up to symmetry) xa1 ∈ E and xa2 ∈
/ E. Then since {x, a1 , b1 , b2 , a2 }
does not induce a dart, x has a neighbor in {b1 , b2 }.
Now, suppose that i = 3. By symmetry, we may assume that xb1 ∈ E. Then since {a1 , x, b1 , a2 , a3 } does
not induce a dart, xa3 ∈ E. Then since {a2 , a1 , x, a3 , a4 } does not induce a P5 , xa4 ∈ E. Then since
{b1 , x, a4 , a3 , b2 } does not induce a dart, xb2 ∈ E. But, then {b1 , a1 , b2 , x, a4 } induces a dart. So, G is
H3 -free.
So, suppose that i = 4. First we show that xb1 ∈
/ E. Suppose not. Then since {x, a1 , a2 , b1 , a3 } and
{x, a1 , a2 , b1 , a4 } do not induce a dart, we have xa3 ∈ E and xa4 ∈ E. But, then {x, a3 , b1 , a4 , a2 } induces
a dart. So, xb1 ∈
/ E, and hence xb2 ∈ E. Then since {x, a1 , a2 , b2 , a3 } does not induce a dart, xa3 ∈ E,
and since {x, b2 , a2 , b1 , a4 } does not induce a P5 , xa4 ∈ E. But, then {a1 , b2 , a3 , x, a4 } induces a dart. So,
G is H4 -free.
Finally, suppose that i = 5. First we show that xb2 ∈
/ E. Suppose not. Then since {x, a1 , a2 , b2 , b3 } and
{x, a1 , a2 , b2 , b4 } do not induce a dart, we have xb3 ∈ E and xb4 ∈ E. But, then {x, b2 , b3 , b4 , a2 } induces
a dart. So, xb2 ∈
/ E, and hence xb1 ∈ E. Then since {x, b1 , a2 , b2 , b3 } and {x, b1 , a2 , b2 , b4 } do not induce
a P5 , we have xb3 ∈ E and xb4 ∈ E. Again, since G is prime, {b3 , b4 } is not a module in G, so there
exists a vertex y ∈ V \ V (H5 ) such that (up to symmetry) yb3 ∈ E and yb4 ∈
/ E. Note that y 6= x.
Then we show that yb2 ∈ E. Suppose not. If ya1 , ya2 ∈ E, then {y, a1 , a2 , b2 , b3 , b4 } induces a H4 , and if
ya1 ∈
/ E, then since {y, b3 , b2 , a1 , b1 } does not induce a P5 , yb1 ∈ E. But, then {b4 , b2 , a1 , b1 , y} induces a
P5 (and similar proof holds when ya2 ∈
/ E). So, yb2 ∈ E. Then ya1 , ya2 ∈
/ E (otherwise, {y, a1 , b2 , b3 , b4 }
or {y, a2 , b2 , b3 , b4 } induces a dart). Then since {x, y, a1 , b2 , b3 , b4 } does not induce a H1 , we have xy ∈
/ E.
Then since {y, b2 , a2 , b1 , x} does not induce a P5 , yb1 ∈ E. But, then {x, a1 , a2 , b1 , y} induces a dart. So,
G is H5 -free.
This shows Lemma 3.2.

Theorem 3.3 Let G be any prime (house, co-dart)-free graph that contains an odd hole of length at
least 7. Then G is triangle-free.
Proof. Let ℓ be the length of any odd hole of length at least 7 in G. It follows that there exist ℓ non-empty
and pairwise disjoint subsets A1 , . . . , Aℓ of V (G) such that, for each i modulo ℓ, the set Ai is complete
to Ai+1 , and there are no other edges between any two of these sets. Let A = A1 ∪ · · · ∪ Aℓ . We choose
these sets so that A is inclusionwise maximal. Let B be the set of vertices of V (G) \ A that are complete
to A. We claim that:
Each Ai is a stable set.
(1)
Proof: Suppose that u, v are two adjacent vertices in Ai . Pick an arbitrary vertex aj ∈ Aj for each
j ∈ {i + 1, i + 2, i + 4}. Then {u, v, ai+1 , ai+2 , ai+4 } induces a co-dart. Thus (1) holds.
For any vertex v ∈ V (G) \ (A ∪ B), the set NA (v) is a stable set.

(2)

Proof: Suppose the contrary. By (1), and since v ∈
/ B, we can pick a vertex ai ∈ Ai for each i such that
v is adjacent to a1 and a2 and not to a3 . Then v is adjacent to ai for all i ∈ {5, ..., ℓ − 1}, for otherwise
{a1 , a2 , a3 , v, ai } induces a co-dart; but then {a1 , v, a5 , a6 , a3 } induces a co-dart. Thus (2) holds.
B = ∅.

5

(3)

Proof: Suppose that B 6= ∅. Consider any b ∈ B and any v ∈ V (G) \ (A ∪ B). For each i pick a vertex
ai ∈ Ai . By (2) and since ℓ is odd, there is an integer j such that v has no neighbor in {aj , aj+1 }, say
j = 1; moreover v has a non-neighbor a in {a4 , a5 }. Then b is adjacent to v, for otherwise {a, b, a1 , a2 , v}
induces a co-dart. This means that B is complete to V (G) \ (A ∪ B). Since B is also complete to A, we
deduce that V (G) \ B is a homogeneous set, which contradicts that G is prime. Thus (3) holds.
G is triangle-free.

(4)

Proof: Suppose that T = {u, v, w} is the vertex-set of a triangle in G. By (1), the graph G[A] is trianglefree. Moreover, by (2) and (3), no triangle of G has two vertices in A. So T contains at most one vertex
from A. Note that G is connected, for otherwise the vertex-set of the component that contains A would
be a proper homogeneous set. So there is a shortest path P from A to T . Let P = p1 -· · · -pk , with p1 ∈ A,
p2 , . . . , pk ∈ V (G) \ A, pk = u, k ≥ 1, and v, w ∈
/ A. We choose T so as to minimize k. We can pick
vertices ai ∈ Ai for each i ∈ {1, ..., ℓ} so that p1 = a1 . If k ≥ 3, then {p1 , pk−1 , u, v, w} induces a co-dart.
So k ≤ 2. Suppose that k = 1. So u = p1 = a1 . By (2) and (3), v and w have no neighbor in {a2 , aℓ }.
If a3 has no neighbor in {v, w}, then {a3 , aℓ , a1 , v, w} induces a co-dart. If a3 has only one neighbor in
{v, w}, then {a3 , a2 , a1 , v, w} induces a house. So a3 is adjacent to both v, w, and {a3 , v, w} is a triangle.
Then we can repeat this argument with a3 , a5 , ... instead of a1 , which leads to a contradiction since ℓ is
odd. Therefore k = 2. So u = p2 . Since ℓ is odd, and by (2) and (3), we may assume that u is adjacent to
a1 and not to a2 and a3 . Then a3 has a neighbor in {v, w}, say v, for otherwise {a3 , a1 , u, v, w} induces
a co-dart, and then a3 is not adjacent to w, for otherwise {a3 , v, w} is a triangle that contradicts the
minimality of k. Then w is not adjacent to a4 , by (2) and (3), and a4 has no neighbor in {u, v}, for
otherwise either {a4 , u, v} is a triangle (contradicting the minimality of k) or {a3 , a4 , u, v, w} induces a
house. But then {a4 , a1 , u, v, w} induces a co-dart, a contradiction. Thus (4) holds, and this completes
the proof of the theorem.

Theorem 3.4 The Weighted Vertex Coloring problem can be solved in polynomial time for (P5 , C5 ,
dart)-free graphs.
Proof. Let G be a (P5 , C5 , dart)-free graph. First suppose that G is prime. If G has no odd anti-hole
of length at least 7, then by SPGT [6], G is perfect. Otherwise, G is O3 -free, by Theorem 3.3. Since
the class of perfect graphs can be recognized in polynomial time [5], and since the WVC problem can
be solved in polynomial time for perfect graphs [15], and for O3 -free graphs [27], WVC can be solved in
polynomial time for G. By Theorem 2.2, the same holds when G is not prime.

A connected prime graph without clique separators is said to be irreducible. By Lemma 3.1 and
Lemma 3.2, it follows that irreducible (P5 , dart)-free graphs are {Hi | i ∈ [5]}-free; see Figure 2.
Theorem 3.5 Let G be an irreducible (P5 , dart)-free graph that contains an induced C5 . Then either
|V (G)| ≤ 18 or G is O3 -free.
Proof. Let G = (V, E) be an irreducible (P5 , dart)-free graph. Suppose that G contains an induced C5
with vertex-set C := {v1 , v2 , v3 , v4 , v5 } and edge-set {vi vi+1 |i ∈ [4]} ∪ {v5 v1 }. We associate the following

6

notation with G, taking the indices modulo 5:
Wi

:= {x ∈ V \ C | NC (x) = {vi−1 , vi+1 }},

Xi

:= {x ∈ V \ C | NC (x) = {vi−1 , vi , vi+1 }},

Yi

:= {x ∈ V \ C | NC (x) = {vi , vi+1 , vi−2 }},

Zi

:= {x ∈ V \ C | NC (x) = V (C) \ {vi }},

T

:= {x ∈ V \ C | NC (x) = V (C)},

R

:= {x ∈ V \ C | NC (x) = ∅}.

Let W := ∪5i=1 Wi , X := ∪5i=1 Xi , Y := ∪5i=1 Yi , and Z := ∪5i=1 Zi .
For every i ∈ [5] (mod 5) the following properties hold true.
(1) If x ∈ V \ C and if NC (x) 6= ∅, then x ∈ W ∪ X ∪ Y ∪ Z ∪ T , as G is P5 -free.
(2) Wi is an independent set.
(3) (a) Xi and Zi are cliques.
(b) Xi is complete to Xi+1 .
(c) Xi is complete to Zi−2 ∪ Zi+2 .
(d) If X 6= ∅, then W = ∅ = Y .
(4) (a) |Yi | ≤ 1.
(b) If Yi 6= ∅, then Yi+1 = ∅ = Yi−1 .
(c) |Y | ≤ 2.
(d) Yi is anticomplete to Yi+2 .
(5) (a) If Z 6= ∅, then W = ∅.
(b) If Zi 6= ∅, for some i, then Y \ Yi+2 = ∅.
(c) Zi is anticomplete to Yi+2 .
(6) (a) If T 6= ∅, then W = ∅ = Y .
(b) [T ] is O3 -free.
(7) (a) If x ∈ W ∪ X ∪ Z ∪ T , then N (x) ∩ R = ∅. So, if R 6= ∅, then since G is connected, Y 6= ∅.
(b) Let x ∈ Yi and y ∈ Yi+2 . Then x and y have the same neighbors in R.
(c) |R| ≤ 1.
(d) If Zi 6= ∅, for some i, then R = ∅.
Proof of the properties (1) − (7). Some of the above properties can be verified routinely and in that case
we omit their proof; however, we do give a proof for those properties which are not trivial.
(2): If there are adjacent vertices x and y in Wi , then {x, y, vi , vi+1 , vi−1 , vi+2 } induces a H4 .
(3:a): If there are non-adjacent vertices x and y in Xi or in Zi , then {x, y, vi , vi+1 , vi+2 } induces a dart.
(3:b): If there are non-adjacent vertices x ∈ Xi and y ∈ Xi+1 , then {x, vi−1 , vi−2 , vi+2 , y} induces a P5 .
(3:c): If there are non-adjacent vertices x ∈ Xi and y ∈ Zi+2 ∪ Zi−2 , say, by symmetry, y ∈ Zi+2 , then
{x, y, vi , vi+1 , vi+2 } induces a dart.
7

(3:d): Suppose not. Let x ∈ X1 ⊆ X and let w ∈ W ∪Y . Then up to symmetry we have the following cases.
If w ∈ W1 , then {x, w, v1 , v2 , v3 , v5 } induces a dart or a H4 . If w ∈ W2 , then {x, w, v1 , v2 , v3 , v4 } induces a
H3 (if xw ∈ E), or {x, v1 , v2 , v5 , w} induces a dart (if xw ∈
/ E). If w ∈ W3 , then {x, w, v1 , v2 , v3 } induces a
dart (if xw ∈ E), or {x, v1 , v2 , v3 , v5 , w} induces a H5 (if xw ∈
/ E). If w ∈ Y1 , then {x, w, v1 , v3 , v4 , v5 } induces a H3 (if xw ∈ E), or {x, w, v1 , v2 , v3 } induces a dart (if xw ∈
/ E). If w ∈ Y2 , then {x, w, v1 , v2 , v4 , v5 }
induces a dart or a H4 . If w ∈ Y3 , then {x, w, v1 , v2 , v4 , v5 } induces a dart or H2 . So, (3:d) holds.
(4:a): Suppose not. Then there are two vertices x and y in Yi . Now, if xy ∈ E, then {x, y, vi+1 , vi+2 ,
vi−2 , vi−1 } induces a H4 , and if xy ∈
/ E, then {x, y, vi , vi+1 , vi+2 } induces a dart. So, (4:a) holds.
(4:b): Suppose not. Then there are two vertices x ∈ Yi and y ∈ Yi+1 ∪Yi−1 , say, up to symmetry, y ∈ Yi+1 .
Now, if xy ∈ E, then {x, vi , vi+1 , y, vi−2 } induces a dart, and if xy ∈
/ E, then {vi , x, vi−2 , vi+2 , y} induces
a P5 . So, (4:b) holds.
(4:c): The proof follows by (4:a) and (4:b).
(4:d): If there are adjacent vertices x ∈ Yi and y ∈ Yi+2 , then {x, y, vi+2 , vi−2 , vi−1 } induces a dart.
(5:a): Suppose not. Let z ∈ Z1 and let w ∈ W . Up to symmetry, we have the following cases. If w ∈ W1 ,
then {z, w, vi+2 , vi+1 , vi } induces a dart (if zw ∈ E), or {vi+2 , vi−2 , z, vi−1 , vi , w} induces a H5 (if zw ∈
/ E).
If w ∈ W2 , then {z, w, vi , vi+1 , vi+2 , vi−2 } induces a H2 (if zw ∈ E), or {z, vi+1 , vi+2 , vi−2 , w} induces a
dart (if zw ∈
/ E). If w ∈ W3 , then {z, w, vi+1 , vi+2 , vi } induces a dart (if zw ∈ E), or {z, vi+2 , vi−2 , vi−1 , w}
induces a dart (if zw ∈
/ E). So, (5:a) holds.
(5:b): Suppose not. Let z ∈ Z1 and let y ∈ Y \ Y3 . Then up to symmetry we have the following cases. If
y ∈ Y1 , then {z, y, vi , vi+2 , vi−2 , vi−1 } induces a H2 (if zy ∈ E), or {z, vi+2 , vi−2 , vi−1 , y} induces a dart
(if zy ∈
/ E). If y ∈ Y2 , then {z, y, vi−1 , vi−2 , vi } induces a dart (if zy ∈ E), or {z, y, vi+1 , vi+2 , vi } induces
a dart (if zy ∈
/ E). Thus, (5:b) holds.
(5:c): If there are adjacent vertices z ∈ Zi and y ∈ Yi+2 , then {z, y, vi−2 , vi−1 , vi+1 } induces a dart.
(6:a): Suppose not. Let t ∈ T . Now, if w ∈ W1 , then {t, w, v1 , v2 , v3 } or {t, w, v1 , v2 , v4 } induces a dart,
and if y ∈ Y1 , then {t, y, v3 , v4 , v5 } or {t, y, v2 , v3 , v5 } induces a dart. Since the other symmetric, these
contradictions show that (6:a) holds. ⋄
(6:b): Suppose to the contrary that [T ] contains a triad, say S := {a, b, c}. Consider the co-connected
component of [T ] containing S. Since G is prime, {a, b} is not a module in G, so there exists a vertex x
in X ∪ Z (by (6:a)) that is adjacent to a and not to b. Since x ∈ X ∪ Z, there exist i, j ∈ [5] such that
vi vj ∈ E, xvi ∈ E and xvj ∈
/ E. Then since {x, a, b, c, vi } does not induce a dart, xc ∈
/ E. But, then
{x, b, c, vi , vj } induces a dart. So, (6:b) holds.
(7:a): Suppose not. Let x ∈ W ∪ X ∪ Z ∪ T be such that N (x) ∩ R 6= ∅. Let y ∈ N (x) ∩ R. Now, if
x ∈ X ∪ Z ∪ T , then there exists i ∈ [5] such that {vi , vi+1 , vi+2 } ⊆ N (x). But, then {vi , vi+1 , vi+2 , x, y}
induces a dart. So, x ∈ W , say x ∈ W1 . Then {y, x, v2 , v3 , v4 } induces a P5 .
(7:b): Suppose not. Then up to symmetry, let r ∈ R be such that rx ∈ E and ry ∈
/ E. But, then since
xy ∈
/ E (by (4 : d)), {r, x, vi+1 , vi+2 , y} induces a P5 .
(7:c): Since G is prime, the proof follows by (7:a) and (7:b).
(7:d): Suppose not. Let z ∈ Zi and r ∈ R. Then by (7 : a), zr ∈
/ E and Y 6= ∅, and by (5 : b),
Y \ Yi+2 = ∅. Thus, Yi+2 6= ∅. Let y ∈ Yi+2 be such that yr ∈ E. Then, by (5 : c), zy ∈
/ E. But, then
{vi−1 , z, vi+2 , y, r} induces a P5 .
Moreover, the following holds.
(8) For every i ∈ [5], we have |Wi | ≤ 2. So, |W | ≤ 10.
Proof: We prove for i = 1. Suppose to the contrary that |W1 | ≥ 3. Then by (2), there exist three mutually
non-adjacent vertices in W1 , say w1 , w2 and w3 . Let G′ be the graph induced by V (C) ∪ {w1 , w2 , w3 },
8

and let W ′ := {v1 , w1 , w2 , w3 }. Since G is prime, V \ V (G′ ) 6= ∅. Then we have the following claim.
Claim 1 Let x ∈ V \ V (G′ ). Suppose that x has a neighbor and a non-neighbor in W ′ , then (i) x has
exactly one neighbor in {v2 , v5 }, and (ii) |N (x) ∩ W ′ | = 1.
Proof of Claim 1. We may assume, up to symmetry, that xw1 ∈ E and xw2 ∈
/ E.
(i): Suppose not. If x has no neighbor in {v2 , v5 }, then since {w2 , v2 , w1 , x, v4 } does not induce a P5 ,
xv4 ∈
/ E. Similarly, since {w2 , v5 , w1 , x, v3 } does not induce a P5 , xv3 ∈
/ E. But, then {x, w1 , v2 , v3 , v4 }
induces a P5 in G, a contradiction. If x is adjacent to both v2 and v5 , then since {x, w1 , v2 , v3 , w2 } does
not induce a dart, xv3 ∈
/ E. But, then {x, v2 , v3 , v5 , w1 , w2 } induces a H4 , which contradicts Lemma 3.2.
So, (i) holds.
(ii): By our assumption, w1 ∈ N (x) ∩ W ′ . We show that N (x) ∩ W ′ = {w1 }. Suppose not. Up
to symmetry, we may assume that xw3 ∈ E. By (i), x has exactly one neighbor in {v2 , v5 }, say, by
symmetry, xv2 ∈ E. Now, {x, v2 , w1 , w3 , w2 } induces a dart. So, (ii) holds.
This shows Claim 1. ⋄
Since G is prime, W ′ is not a module. So, by Claim 1(ii) and by symmetry, there exist vertices x, y
and z in V \ V (G′ ) such that N (x) ∩ W ′ = {v1 }, N (y) ∩ W ′ = {w1 }, and N (z) ∩ W ′ = {w2 }. Then by
Claim 1(i), two of the vertices in {x, y, z} have the same neighbor in {v2 , v5 }. Up to symmetry, let x and
y have the same neighbor v2 . Again by Claim 1(i), xv5 ∈
/ E and yv5 ∈
/ E. Then since {x, y, v1 , v2 , w3 }
does not induce a dart, xy ∈
/ E. Also, since the subgraph induced by {x, y, v1 , v2 , v3 , w1 , w3 } does not
contain a dart, xv3 ∈
/ E and yv3 ∈
/ E. Then since the subgraph induced by {x, y, v1 , v2 , v3 , v4 , w1 } does
not contain a P5 , we have xv4 ∈ E and yv4 ∈ E. But, then {v1 , x, v4 , y, w1 } induces a P5 . Thus, (8)
holds.
Now, we claim that:
(9) [C ∪ X ∪ Z] is O3 -free.
Proof: Suppose to the contrary that [C ∪X ∪Z] contains a triad, say S := {a, b, c}. Then by the definitions
of X and Z, S has at most one vertex from C. If v1 (:= a) ∈ S (say), then b and c belong to X3 ∪ X4 ∪ Z1 ,
which is impossible, by using (3). So, suppose that none of the vertices from V (C) belongs to S. Then
by using (3), we may have the following cases (the other cases are either similar or symmetric): (i) If
a ∈ X1 , b ∈ X3 ∪ Z1 and c ∈ Z2 , then {a, v1 , c, v3 , b} induces a P5 , (ii) if a ∈ X1 , b ∈ Z2 and c ∈ Z5 ,
then {v3 , v4 , b, c, v1 , a} induces a H3 , and (iii) if a ∈ Z1 , b ∈ Z2 and c ∈ Z3 ∪ Z4 , then {a, b, c, v1 , v5 } or
{a, b, c, v4 , v5 } induces a dart. Thus, (9) holds.
Now, if X ∪ Z ∪ T = ∅, then by the properties (4:c) and (7:d), and by (8), it follows that |V | =
|C ∪ W ∪ Y ∪ R| ≤ 10 + 5 + 2 + 1 = 18. So, suppose that X ∪ Z ∪ T 6= ∅. We prove the theorem in three
cases as follows. Suppose that T 6= ∅. Then we show that G is O3 -free. Suppose to the contrary that G
contains a triad, say S := {a, b, c}. Since T 6= ∅, we have W = Y = ∅, by (6). So, R = ∅ (by (7:a)). Also,
since [C ∪ X ∪ Z] is O3 -free, by (9), at least one vertex from T is in S, and hence none of the vertices
from C belong to S. Since [T ] is O3 -free, by the above properties, we may have the following cases (the
other cases are symmetric):
(i) a ∈ X1 , b ∈ X3 and c ∈ T . Then {a, v1 , c, v3 , b} induces a P5 .
(ii) a ∈ X1 , b ∈ T and c ∈ T . Then {a, b, c, v2 , v3 } induces a dart.
(iii) a ∈ Z1 , b ∈ Z2 ∪ Z3 ∪ T and c ∈ T . Then {a, b, c, v1 , v5 } induces a dart.
(iv) a ∈ X1 , b ∈ Z1 ∪ Z2 , and c ∈ T . Then {a, b, c, v4 , v5 } induces a dart.
These contradictions show that G is O3 -free. Therefore we may assume that T = ∅. If X 6= ∅, then since
9

W = Y = ∅ (by (3:d)), R = ∅ (by (7:a)), it follows by (9) that G is O3 -free. So, we may suppose that
T = X = ∅. Thus, Z 6= ∅, and let z ∈ Z1 . Then by (5:a) and (5:b), W = ∅ and Y \ Y3 = ∅. Also, by (7:d),
R = ∅. If Y3 = ∅, then by (9), G is O3 -free. So, suppose that Y3 6= ∅. Again, by (5:a), Z \ Z1 = ∅. Then
since Z1 is a clique, and any vertex in Y3 is adjacent to v1 , it follows that G is O3 -free. This completes
the proof of Theorem 3.5.

Finally we can prove the main result of this section.
Theorem 3.6 The Weighted Vertex Coloring problem can be solved in polynomial time for (P5 ,
dart)-free graphs.
Proof. Since the class of perfect graphs can be recognized in polynomial time [5], and since the WVC
problem can be solved in polynomial time for perfect graphs [15], for O3 -free graphs [27], and for the
class of graphs having at most c vertices (for each fixed c) [27], the theorem follows by Theorems 2.1, 2.2,
3.4 and Theorem 3.5.


4

WVC for (P5 , banner)-free graphs

The main result of this section is the following.
Theorem 4.1 The Weighted Vertex Coloring problem can be solved in polynomial time for (P5 ,
banner)-free graphs.
We first establish a structure theorem for the complement graph of a (P5 , banner)-free graph. The
complement of a banner is called a hammer. See Figure 1.
Theorem 4.2 Let G be any prime (hammer, house)-free graph. Then G is either perfect, or triangle-free.
Proof. Let G be a prime (house, hammer)-free graph, and suppose that G is not perfect. By the Strong
Perfect Graph Theorem G contains an odd hole or an odd antihole of length at least 5. However, every
antihole of length at least 6 contains a house. So G contains a hole, of length ℓ ≥ 5. It follows that there
exist ℓ non-empty and pairwise disjoint subsets A1 , . . . , Aℓ of V (G) such that, for each i modulo ℓ, the set
Ai is complete to Ai+1 , and there are no other edges between any two of these sets. Let A = A1 ∪ · · · ∪ Aℓ .
We choose these sets so that A is inclusionwise maximal. Let B be the set of vertices of V (G) \ A that
are complete to A. We first claim that:
Each Ai is a stable set.

(1)

Proof: Suppose that u and v are two adjacent vertices in Ai . Pick an arbitrary vertex aj ∈ Aj for each
j ∈ {i + 1, i + 2, i + 3}. Then {u, v, ai+1 , ai+2 , ai+3 } induces a hammer. Thus (1) holds.
Now we claim that:
For any vertex v ∈ V (G) \ (A ∪ B), the set NA (v) is a stable set.

(2)

Proof: Suppose the contrary. By (1) there is an integer i such that v has a neighbor ai ∈ Ai and a
neighbor ai+1 ∈ Ai+1 . Consider arbitrary vertices ai+2 ∈ Ai+2 and ai+3 ∈ Ai+3 . Then v is adjacent
to ai+2 , for otherwise {v, ai , ai+1 , ai+2 , ai+3 } induces a hammer or a house (depending on the adjacency
between v and ai+3 ). Now we can repeat this argument with i + 1 and so on, which implies that v ∈ B,
a contradiction. Thus (2) holds.
10

Now we claim that:
B = ∅.

(3)

Proof: Suppose that B 6= ∅. Let H be the component of G \ B that contains A. By the hypothesis,
V (H) is not a proper homogeneous set, which implies that there exist non-adjacent vertices b ∈ B and
x ∈ V (H). By the definition of H there is a shortest path p1 -· · · -pk in H with p1 ∈ A and pk = x, and
we choose the pair b, x so as to minimize k. We have k ≥ 2 since x ∈
/ A. We can pick vertices ai ∈ Ai for
each i ∈ {1, . . . , ℓ} so that p2 has a neighbor in the set {a1 , ..., aℓ }. Since ℓ is odd, and by (2), p2 has two
consecutive non-neighbors in that set, so, up to relabeling, we may assume that p2 is adjacent to a1 and
not adjacent to a2 and a3 . Then b is adjacent to p2 , for otherwise {p2 , a1 , b, a3 , a4 } induces a hammer or
a house (depending on the adjacency between p2 and a4 ). Hence there is an integer j ≤ k such that b is
adjacent to pj and not to pj+1 . But then {pj+1 , pj , b, a2 , a3 } induces a hammer. Thus (3) holds.
Now we claim that:
G is triangle-free.

(4)

Proof: Suppose that T = {u, v, w} is the vertex-set of a triangle in G. By (1), the graph G[A] is trianglefree. Moreover, by (2), no triangle of G has two vertices in A. So T contains at most one vertex from
A. Note that G is connected, for otherwise the vertex-set of the component that contains A would be a
proper homogeneous set and not a stable set. So there is a shortest path P from A to T . Let P = p1 · · · -pk , with p1 ∈ A, p2 , . . . , pk ∈ V (G) \ A, pk = u, k ≥ 1, and v, w ∈
/ A. We choose T so as to minimize
k. If k = 1, let p2 = v. We can pick vertices ai ∈ Ai for each i ∈ {1, ..., ℓ} so that p2 has a neighbor
in the set {a1 , ..., aℓ }. Since ℓ is odd, and by (2), we may assume that p2 is adjacent to a1 and not to
a2 and a3 . Suppose that k = 1 (so u = p1 = a1 and p2 = v). Then {u, v, w, a2 , a3 } induces a hammer
or a house (depending on w, a3 ). Now suppose that k ≥ 2. By the minimality of k, the vertices v, w
have no neighbor in {p1 , ..., pk−1 }. Suppose that k = 2. If any of v, w is adjacent to a2 , then both are,
for otherwise {v, w, u, p1 , a2 } induces a house; but then {v, w, a2 } is a triangle, so we should have k = 1.
Hence k ≥ 3. But then {v, w, u, pk−1 , pk−2 } induces a hammer. Thus (4) holds. This completes the proof
of the theorem.

Proof of Theorem 4.1. Since the class of perfect graphs can be recognized in polynomial time [5], and
since the WVC problem can be solved in polynomial time for perfect graphs [15] and for O3 -free graphs
[27], the theorem follows by Theorems 2.2 and 4.2.


5

WVC for (P5 , bull)-free graphs

In this section, we show the following result. This was mentioned as an open problem in [4].
Theorem 5.1 The Weighted Vertex Coloring problem can be solved in polynomial time for (P5 ,
bull)-free graphs.
We first establish a structure theorem for the complement graph of a (P5 , bull)-free graph. Note that
the bull is a self-complementary graph.
Theorem 5.2 Let G be any prime (house, bull)-free graph. Then either G is C5 -free and P5 -free, or G
is triangle-free.

11

Proof. Let G be a prime (house, bull)-free graph, and suppose that G contains a P5 or a C5 . So there
exist five non-empty and pairwise disjoint subsets A1 , . . . , A5 of V (G) such that the following properties
hold, with subscripts modulo 5:
• For each i ∈ {1, 2, 3, 4}, Ai is complete to Ai+1 .
• For each i ∈ {1, 2, 3, 4, 5}, Ai is anticomplete to Ai+2 .
• A5 is either complete or anticomplete to A1 .
Note that if A5 is complete to A1 the five sets play symmetric roles. Let A = A1 ∪ · · · ∪ A5 . We choose
these sets so that A is inclusionwise maximal. Let B be the set of vertices of V (G) \ A that are complete
to A. We first claim that:
For any vertex v ∈ V (G) \ (A ∪ B) and any i ∈ {1, . . . , 5}, v is anticomplete to at least
one of Ai , Ai+1 , Ai+2 , Ai+3 .

(1)

Proof: For each i ∈ {1, ..., 5}, let ai be a neighbor of v in Ai (if any) and let zi be a non-neighbor of
v in Ai (if any). Suppose that v has neighbors in four sets Ai , Ai+1 , Ai+2 , Ai+3 . Up to symmetry we
may assume that i ∈ {1, 3, 4}. If i = 1, then v is complete to A5 , for otherwise {a1 , v, a3 , a4 , z5 } induces
either a house or a bull (depending on the adjacency between a1 and z5 ). If i = 3, then v is complete
to A2 , for otherwise {a1 , z2 , a3 , a4 , v} induces a house. If i = 4, then v is complete to A3 , for otherwise
{a1 , a2 , z3 , a4 , v} induces a house. In all cases v is complete to Ai−1 , so v has neighbors in all five sets.
Repeating this argument with each i we obtain that v ∈ B, a contradiction. Thus (1) holds.
Now we claim that:
For any vertex v ∈ V (G) \ (A ∪ B) and any i ∈ {1, . . . , 4}, v is anticomplete to at least one
of Ai and Ai+1 . Also, if A5 is complete to A1 , then v is anticomplete to one of A1 , A5 .

(2)

Proof: For each i ∈ {1, ..., 5}, let ai be a neighbor of v in Ai (if any) and let zi be a non-neighbor of v in
Ai (if any). Suppose that v has neighbors in two consecutive sets Ai and Ai+1 .
First suppose that A5 is complete to A1 . Up to symmetry, we may assume that i = 1. Then v is complete
to A5 or to A3 , for otherwise {z5 , a1 , v, a2 , z3 } induces a bull. By symmetry we may assume that v is
complete to A3 ; and it follows from (1) that v has no neighbor in A5 ∪ A4 . Moreover v is complete to
A1 , for otherwise {z1 , a2 , v, a3 , z4 } induces a bull. But now the sets A1 , A2 ∪ {v}, A3 , A4 , A5 contradict
the maximality of A.
Therefore we may assume that A5 is anticomplete to A1 . Up to symmetry we have i ∈ {1, 2}. Suppose
that i = 1. Suppose that v has a non-neighbor z3 ∈ A3 . Then v is anticomplete to A4 , for otherwise
{a1 , a2 , z3 , a4 , v} induces a house; and v is anticomplete to A5 , for otherwise {z3 , a2 , a1 , v, a5 } induces a
bull; and v is complete to A2 , for otherwise either {v, a1 , z2 , z3 , a2 } induces a house (if a2 z2 ∈
/ E(G)) or
{v, a2 , z2 , z3 , z4 } induces a bull (if a2 z2 ∈ E(G)). But now the sets A1 ∪ {v}, A2 , A3 , A4 , A5 contradict the
maximality of A. Hence v is complete to A3 . By (1), v has no neighbor in A4 ∪ A5 . Then v is complete
to A1 , for otherwise {z1 , a2 , v, a3 , z4 } induces a bull. But now the sets A1 , A2 ∪ {v}, A3 , A4 , A5 contradict
the maximality of A. Finally suppose that i = 2. By the preceding point (the case i = 1) we may assume
that v is anticomplete to A1 . Then v is complete to A4 , for otherwise {z1 , a2 , v, a3 , z4 } induces a bull. By
(1), v is anticomplete to A5 . By symmetry, v is complete to A2 . But now the sets A1 , A2 , A3 ∪ {v}, A4 , A5
contradict the maximality of A. Thus (2) holds.
Now we claim that:
B = ∅.
12

(3)

Proof: Suppose that B 6= ∅. Let H be the component of G \ B that contains A. Since G is prime, V (H) is
not a proper homogeneous set, which implies that there exist non-adjacent vertices b ∈ B and x ∈ V (H).
By the definition of H there is a shortest path p1 -· · · -pk in H with p1 ∈ A and pk = x, and we choose
the pair b, x so as to minimize k. We have k ≥ 2 since x ∈
/ A. We can pick vertices ai ∈ Ai for each
i ∈ {1, . . . , 5} so that p2 has a neighbor in {a1 , ..., a5 }. We choose three vertices u, v, w ∈ {a1 , ..., a5 } so
that: (i) uv is the only edge in G[u, v, w], and (ii) u is the only neighbor of p2 among them; indeed we
can find u, v, w as follows. If A5 is complete to A1 , then by (2) and symmetry we may assume that p2 is
adjacent to a1 and has no neighbor in {a2 , a4 , a5 }, and we set u = a1 , v = a2 , w = a4 . Suppose that A5 is
anticomplete to A1 . If p2 is adjacent to a1 or a2 , let {u, v} = {a1 , a2 }, and let w be a non-neighbor of p2
in {a4 , a5 } (w exists by (2)). The case when p2 is adjacent to a5 or a4 is symmetric. Finally if the only
neighbor of p2 in {a1 , ..., a5 } is a3 , then let u = a3 , v = a2 and w = a5 . In either case, we see that b is
adjacent to p2 , for otherwise {p2 , u, v, b, w} induces a bull. So k ≥ 3. By the minimality of k, the vertices
p3 , ..., pk have no neighbor in A, and b is adjacent to each of p2 , ..., pk−1 . Then {pk , pk−1 , pk−2 , b, w}
induces a bull, a contradiction. Thus (3) holds.
Now we claim that:
For each i ∈ {1, ..., 5}, Ai is a stable set.

(4)

Proof: Suppose, up to symmetry, that Ai is not a stable set for some i ∈ {1, 2, 3}. So G[Ai ] has a
component H of size at least 2. Since G is prime, V (H) is not a homogeneous set, so there is a vertex
z ∈ V (G) \ V (H) and two vertices x, y ∈ V (H) such that z is adjacent to y and not to x, and since H is
connected we may choose x and y adjacent. By the definition of H we have z ∈
/ Ai . Since z is adjacent
to y and not to x, we have z ∈
/ A ∪ B. Pick any a′ ∈ Ai+1 and a′′ ∈ Ai+2 . By (2) and since z has a
neighbor in Ai , z is not adjacent to a′ . Then {z, y, x, a′ , a′′ } induces a bull or a house (depending on the
adjacency between z and a′′ ), a contradiction. Thus (4) holds.
Now we claim that:
G is triangle-free.

(5)

Proof: Suppose that T = {u, v, w} is the vertex-set of a triangle in G. By (4), the graph G[A] is trianglefree. Moreover, by (2), no triangle of G has two vertices in A. So T contains at most one vertex from
A. Note that G is connected, for otherwise the vertex-set of the component that contains A would be a
proper homogeneous set. So there is a shortest path P from A to T . Let P = p1 -· · · -pk , with p1 ∈ A,
p2 , . . . , pk ∈ V (G)\A, pk = u, k ≥ 1, and v, w ∈
/ A. We choose T so as to minimize k. We can pick vertices
ai ∈ Ai for each i ∈ {1, ..., 5} so that, up to symmetry p1 = ai for some i ∈ {1, 2, 3}. Let p0 = ai+1 . Let
U be the set of neighbor of u, and let H be the component of G[U ] that contains v and w. Since V (H)
is not a homogeneous set, there are vertices x, y ∈ V (H) and z ∈ V (G) \ V (H) such that z is adjacent to
y and not to x, and since H is connected we may choose such x and y adjacent. By the definition of H,
the vertex z is not adjacent to u. If x is adjacent to pk−1 , then either k = 1 and (2) is violated (because
x is adjacent to p1 and p0 ), or k ≥ 2 and {pk−1 , pk , x} is a triangle that contradicts the minimality of k.
So x is not adjacent to pk−1 , and similarly y is not adjacent to pk−1 . But then {z, y, x, u, pk−1} induces a
bull or a house (depending on the adjacency between z and pk−1 ), a contradiction. Thus (5) holds. This
completes the proof of the theorem.

Proof of Theorem 5.1. Since the WVC problem can be solved in polynomial time for (P5 , C5 , house)-free
graphs [7], and for O3 -free graphs [27], the theorem follows by Theorem 2.2 and Theorem 5.2.


13

6

WVC for (fork, bull)-free graphs

In this section, we show how the WVC problem can be solved in polynomial time in the class of (fork,
bull)-free graphs.
The following lemma is from [8].
Lemma 6.1 ([8]) In a bull-free graph G, let B = {v1 , ..., vℓ } be the vertex-set of a hole of length ℓ ≥ 6,
with edges vi vi+1 for all i modulo ℓ. Then for every vertex x in V (G) \ B the set NB (x) is either a stable
set, or equal to B, or equal to {vi−1 , vi , vi+1 } for some i, or equal to {vi−1 , vi , vi+1 , vi+3 } for some i and
in this last case ℓ = 6.
A wheel (resp. a fan) is a graph that consists of a hole H of length at least six (resp. a path H on six
vertices) plus a vertex that is complete to V (H). An umbrella (resp. a parasol ) is a graph that consists
of a hole H on five vertices (resp. a path H on five vertices) plus a sixth vertex that is complete to V (H),
and a seventh vertex that is adjacent to the sixth vertex only. In a wheel (resp. fan, umbrella, parasol)
the hole or path H is called the rim.
The following lemma summarizes results from [11, 20, 24, 30].
Lemma 6.2 Let G be a bull-free graph that contains as an induced subgraph either a wheel, or an umbrella, or a parasol, or a fan. Then G has a proper homogeneous set that contains the rim of this subgraph.
Theorem 6.3 Let G be a prime (fork, bull)-free graph that contains a hole of length ℓ ≥ 6. Then G is
either a hole of length ℓ or a bipartite graph.
Proof. Let B = {v1 , ..., vℓ } be the vertex-set of such a cycle, with edges vi vi+1 for all i modulo ℓ.
For any J ⊆ {1, ..., ℓ}, let SJ = {x ∈ V (G) \ B | N (x) ∩ B = {vj | j ∈ J}} (and we will write, for
example, S123 instead of S{1,2,3} ). Let A = S1,2,...,ℓ and F = S∅ . We claim that:
S
V (G) = B ∪ A ∪ F ∪ ( ℓi=1 Si−1,i,i+1 ) ∪ (S135 ∪ S246 ).
Moreover, if S135 ∪ S246 6= ∅, then ℓ = 6.

(1)

Proof: Consider any vertex x ∈ V (G) \ (A ∪ F ), and let X = NB (x). So ∅ =
6 X 6= B. Since G is
bull-free, Lemma 6.1 implies that X is either (i) a stable set, or (ii) equal to {vi−1 , vi , vi+1 } for some i,
or (iii) equal to {vi−1 , vi , vi+1 , vi+3 } for some i and ℓ = 6. Suppose that (i) holds, and say v1 ∈ X. Then
vℓ , v2 ∈
/ X since X is stable, and v3 ∈ X, for otherwise {v3 , v2 , v1 , vℓ , x} induces a fork. Repeating this
argument, we see that x is adjacent to every second vertex of B, which implies that ℓ is even. Moreover,
if ℓ ≥ 8, then {v5 , x, v1 , v2 , vℓ } induces a fork. So ℓ = 6, and x ∈ S135 ∪ S246 , and the second sentence
of (1) holds. Now suppose that (ii) holds. Then x ∈ Si−1,i,i+1 . Finally suppose that (iii) holds. Then
{vi , x, vi+3 , vi+2 , vi+4 } induces a fork. So (1) holds. In particular, every vertex in V (G) \ B has either
zero, three or ℓ neighbors in B.
Next:
A = ∅.
(2)
For otherwise the union of B and any vertex in A induces a wheel, which, by Lemma 6.2, contradicts the
fact that G is prime.
Next:
Si−1,i,i+1 = ∅, for all i.
(3)
Suppose that there is a vertex u ∈ S123 . Let Y be the set of vertices that are complete to {v1 , v3 } and
anticomplete to B \ {v1 , v2 , v3 }. So v2 , u ∈ Y . Let Z be the vertex-set of the component of G[Y ] that
14

contains v2 and u. Since G is prime, Z is not a homogeneous set, so there are vertices y, z ∈ Z and a
vertex w ∈ V (G) \ Z that is adjacent to y and not to z. Let By be the vertex-set of the hole induced by
(B \ {v2 }) ∪ {y} and let Bz be defined similarly. Then there is an integer p such that w has p neighbors in
By and p − 1 neighbors in Bz , which contradicts the analogue of (1) applied to By and Bz . So (3) holds.
Next:
F = ∅,
(4)
Proof: Suppose the contrary. Let f ∈ F . Since G is prime it is connected, so there is an edge f u for some
u ∈ V (G) \ F . By (2) and (3), we have u ∈ S135 ∪ S246 and ℓ = 6, say u ∈ S135 . But then {f, u, v1 , v2 , v6 }
induces a fork. So, (4) holds.
Now it follows from (1), (2), (3) and (4) that if S135 ∪ S246 = ∅, then V (G) = B, so G is a hole of
length ℓ.
Finally let us assume that S135 ∪ S246 6= ∅. So ℓ = 6. We claim that:
S135 and S246 are stable sets.

(5)

Proof: Suppose on the contrary that S135 is not a stable set. Let Y be the vertex-set of a component of
G[S135 ] of size at least 2. Since G is prime, Y is not a homogeneous set, so there are vertices y, z ∈ Y
and a vertex w ∈ V (G) \ Y that is adjacent to y and not to z, and since Y is connected we may choose
y and z adjacent. By (1), (2), (3) and (4) we have w ∈ S246 . But then {z, y, w, v2 , v4 } induces a fork. So
(5) holds.
By (5), V (G) can be partitioned into the two stable sets S135 ∪ {v2 , v4 , v6 } and S246 ∪ {v1 , v3 , v5 }, so
G is a bipartite graph. This completes the proof of the theorem.

By the preceding theorem, the WVC problem in case the graph contains a hole of length at least 6
can be reduced to the same problem in a graph that is either bipartite or an odd hole. If the graph is
bipartite it is perfect, so we can use the algorithm from [15]. If it is an odd hole, the details can be worked
out directly, as explained in the following lemma. A hyperhole is any graph H such that V (H) can be
partitioned into ℓ cliques A1 , . . . , Aℓ (for some integer ℓ ≥ 4) such that for each i modulo ℓ the set Ai is
complete to Ai−1 ∪ Ai+1 and anticomplete to Ai+2 ∪ Ai+3 ∪ · · · ∪ Ai−3 ∪ Ai−2 . The weighted coloring
problem on a hole of length ℓ, where the i-th vertex has integer weight wi , is equivalent to coloring a
hyperhole of length ℓ where the i-th set Ai has size wi .
Lemma 6.4 Let H be a hyperhole, where V (H) is partitioned into sets A1 , ..., Aℓ as above, with ℓ odd,
(H)|
⌉}.
ℓ ≥ 5. Then χ(G) = max{ω(H), ⌈ 2|Vℓ−1
|V (H)|
Proof. Let m = ℓ−1
2 , and let r(H) = max{ω(H), ⌈ m ⌉}. Clearly we have χ(H) ≥ ω(H), and also
|V (H)|
χ(H) ≥ ⌈ m ⌉ since m is the maximum size of a stable set in H. So χ(H) ≥ r(H). Now let us show
that H admits a coloring of size r(H). We prove this by induction on V (H). Note that the maximal
cliques of H are the sets Ai ∪ Ai+1 , i = 1, ..., ℓ.
First suppose that there is an integer i such that |Ai ∪ Ai+1 | < ω(G), say i = ℓ. For each even
j ∈ {2, 4, ..., ℓ − 1} pick a vertex aj ∈ Aj , and let S = {a2 , a4 , ..., aℓ−1 }. Then S is a stable set, and S
(H)|
meets every ω(H)-clique of H, so ω(H \ S) = ω(H) − 1. Moreover |S| = m, so ⌈ |V (H\S)|
⌉ = ⌈ |V m
⌉ − 1.
m
It follows that r(H \ S) = r(H) − 1. If Aj = {aj } for some even j, then H \ S is a perfect graph (indeed
a chordal graph), so χ(H \ S) = ω(H \ S) = r(H \ S). Otherwise H \ S is a hyperhole of length ℓ, and,
by the induction hypothesis, χ(H \ S) = r(H \ S). In either case, we can take any χ(H \ S)-coloring of
H \ S and add S as a new color class, and we obtain a coloring of H with r(H) colors.

15

Now suppose that |Ai ∪ Ai+1 | = ω(G) for all i. Since ℓ is odd, this means that the numbers |Ai |
(i ∈ {1, ..., ℓ}) are all equal to some integer q. Then ω(H) = 2q and |V (H)| = ℓq = (2m + 1)q, so
(H)|
(H)|
⌉, and so r(H) = ⌈ |V m
⌉. Let S be defined as above. Then, as above, we have
ω(H) < ⌈ |V m
|V (H\S)|
|V (H)|
⌈ m ⌉ = ⌈ m ⌉ − 1. Hence r(H \ S) = r(H) − 1, and again we can take any χ(H \ S)-coloring of
H \ S and add S as a new color class, and we obtain a coloring of H with r(H) colors.

Theorem 6.5 Let G be a prime (fork, bull)-free graph that contains no hole of length at least 6. Suppose
that G contains a P5 v1 -v2 -v3 -v4 -v5 . Then either G has a clique cutset, or there is an optimal coloring
of G in which {v1 , v3 , v5 } is a color class.
Proof. Let B = {v1 , ..., v5 }. For any J ⊆ {1, ..., 5}, let SJ = {x ∈ V (G) \ B | N (x) ∩ B = {vj | j ∈ J}}.
Let A = S1,2,3,4,5 and F = S∅ . We claim that:
V (G) = B ∪ A ∪ F ∪ S1 ∪ S5 ∪ S12 ∪ S45 ∪ S24 ∪
∪S123 ∪ S234 ∪ S345 ∪ S135 ∪ S1345 ∪ S1235 .

(1)

Proof: Consider any vertex x ∈ V (G) \ (A ∪ F ), and let X = NB (x); so 1 ≤ |X| ≤ 4. Suppose that
|X| = 1, so X = {vi } for some i. If i ∈ {2, 3}, then {vi+2 , vi+1 , vi , vi−1 , x} induces a fork. Hence, by
symmetry, i ∈ {1, 5} and so x ∈ S1 ∪ S5 .
Now suppose that |X| = 2. Up to symmetry we have the following six cases. (i) X = {v1 , v2 }. Then x ∈
S12 . (ii) X = {v1 , v3 }. Then {v5 , v4 , v3 , v2 , x} induces a fork. (iii) X = {v1 , v4 }. Then {v1 , x, v4 , v3 , v5 }
induces a fork. (iv) X = {v1 , v5 }. Then B ∪ {x} induces a hole of length 6, a contradiction. (v) X =
{v2 , v3 }. Then {v1 , v2 , x, v3 , v4 } induces a bull. (vi) X = {v2 , v4 }. Then x ∈ S24 .
Now suppose that |X| = 3. Up to symmetry we have the following four cases. (i) X = {vi , vi+1 , vi+2 }
for some i ∈ {1, 2, 3}. Then x ∈ S123 ∪ S234 ∪ S345 . (ii) X = {v1 , v2 , vi } for some i ∈ {4, 5}. If i = 4,
then {v1 , x, v4 , v3 , v5 } induces a fork. If i = 5, then {v3 , v2 , v1 , x, v5 } induces a bull. (iii) X = {v2 , v3 , v5 }.
Then {v1 , v2 , x, v3 , v4 } induces a bull. (iv) X = {v1 , v3 , v5 }. Then x ∈ S135 .
Finally suppose that |X| = 4, and let vj be the non-neighbor of x in B. If j = 1 or 3, then {v1 , v2 , v3 , x, v5 }
induces a bull. Similarly there is a bull if j = 5. So j ∈ {2, 4}, and so x ∈ S1345 ∪ S1235 . Thus (1) holds.
Define the following sets. Let:
V1

:= {v1 } ∪ S12 .

V2

:= {v2 } ∪ S123 .

V3

:= {v3 } ∪ S24 ∪ S234 .

V4

:= {v4 } ∪ S345 .

V5

:= {v5 } ∪ S345 .

′

A

:= A ∪ S135 ∪ S1235 ∪ S1345 .

Now we claim that:
V1 , V3 and V5 are homogeneous sets.

(2)

Proof: Suppose that V1 is not a homogeneous set. So there are vertices y, z ∈ V1 and a vertex w ∈
V (G) \ V1 that is adjacent to y and not to z. Clearly w ∈
/ {v2 , v3 , v4 , v5 }. Then yz ∈ E(G), for
otherwise {v4 , v3 , v2 , y, z} induces a fork. Suppose that wv2 ∈
/ E(G). Then wv3 ∈ E(G), for otherwise
{w, y, z, v2 , v3 } induces a bull; and wv5 ∈
/ E(G), for otherwise {z, y, w, v3 , v5 } induces a fork; and wv4 ∈
/
16

E(G), for otherwise {v2 , v3 , w, v4 , v5 } induces a bull. But then {v5 , v4 , v3 , v2 , w} induces a fork. Hence
wv2 ∈ E(G). Suppose that wv3 ∈ E(G). Then wv4 ∈ E(G), for otherwise {z, v2 , w, v3 , v4 } induces a bull;
and wv5 ∈ E(G), for otherwise {y, w, v3 , v4 , v5 } induces a bull. But then {z, y, w, v3 , v5 } induces a fork.
Hence wv3 ∈
/ E(G). Then, by (1), w ∈ S24 . But, then {y, w, v3 , v4 , v5 } induces a fork, a contradiction.
So V1 is a homogeneous set, and similarly V5 is a homogeneous set.
Now suppose that V3 is not a homogeneous set. So there are vertices y, zi ∈ V3 and a vertex w ∈ V (G)\V3
that is adjacent to y and not to z. Clearly w ∈
/ {v1 , v2 , v4 , v5 }, and w ∈
/ S24 ∪ S234 . The vertex w has a
neighbor in {v1 , v2 }, for otherwise {v1 , v2 , w, y, z} induces a fork or a bull (depending on the adjacency
between y and z), and similarly w has a neighbor in {v4 , v5 }. So, by (1), w ∈ S135 ∪ S1345 ∪ S1235 . If
w ∈ S135 , then {v1 , v2 , z, v4 , v5 , w} induces a hole of length 6, and if w ∈ S1235 ∪S1345 , then {v1 , v2 , y, z, v5 }
or {v4 , v5 , y, z, v1 } induces a bull. Thus (2) holds.
V2 is anticomplete to V4 .

(3)

Proof: Suppose that there is an edge st with s ∈ V2 and t ∈ V4 . The definition of these sets implies that
s ∈ S123 and t ∈ S345 . Then {v1 , s, v3 , t, v5 } induces a bull, a contradiction. Thus (3) holds.
It follows from (2) and (3) that for each i ∈ {1, 2, 3, 4} the set Vi is complete to Vi+1 and that there
is no other edge between any two Vi ’s. Moreover, since G is quasi-prime, each of V1 , V3 , V5 is a clique.
(Also, since V3 is a clique, we have S24 = ∅.) Claim (2) also implies that V1 ∪ V3 ∪ V5 is complete to A′ .
Now we claim that:
S1 is anticomplete to V2 ∪ V3 ∪ V4 ∪ V5 ∪ A′ . Similarly, S5 is anticomplete to V1 ∪ V2 ∪
V3 ∪ V4 ∪ A′ .

(4)

Proof: Suppose, up to symmetry, that there is an edge st with s ∈ S1 and t ∈ V2 ∪ V3 ∪ V4 ∪ V5 ∪ A′ . If
t ∈ V3 ∪ V5 , then (2) is contradicted since sv3 , sv5 ∈
/ E(G). If t ∈ V4 , then t ∈ S345 , and {s, t, v4 , v3 , v2 }
induces a bull. So, {v1 , v2 } ⊆ NB (t). Then since {v2 , v3 , v4 , s, t} does not induce a fork or a bull, we see
that, by (1), NB (t) = B. But, then B ∪ {s, t} induces a 6-fan, which contradicts Lemma 6.2. Thus (4)
holds.
F is anticomplete V1 ∪ V2 ∪ V3 ∪ V4 ∪ V5 ∪ A′ .

(5)
′

Proof: Suppose on the contrary that there is an edge f t with f ∈ F and t ∈ V1 ∪ V2 ∪ V3 ∪ V4 ∪ V5 ∪ A . If
t ∈ V1 ∪ V3 ∪ V5 , then (2) is contradicted since f has no neighbor in B. If t ∈ S123 ∪ S345 ∪ S1235 ∪ S1345 ,
then there is i ∈ {1, 2, 3} such that {f, t, vi , vi+1 , vi+2 } induces a bull. If t ∈ S135 , then {f, t, v3 , v2 , v4 }
induces a fork. If t ∈ A, then B ∪ {t, f } induces a parasol, which contradicts Lemma 6.2. Thus (5) holds.
No component of G[F ∪ S1 ∪ S5 ] contains vertices from both S1 , S5 .

(6)

Proof: In the opposite case, there is a chordless path P with an end in S1 , an end in S5 , and interior in
F . Then V (P ) ∪ B induces a hole of length at least 7, a contradiction. Thus (6) holds.
Any component H of G[S1 ∪ S5 ∪ F ] satisfies either N (V (H)) ⊆ V1 or N (V (H)) ⊆ V5 .

(7)

Proof: This follows immediately from (4), (5) and (6).
Suppose that S1 ∪ S5 ∪ F 6= ∅. So there exists a component H of G[S1 ∪ S5 ∪ F ] such that, by (4)—(7)
and up to symmetry, N (V (H)) ⊆ V1 . So V1 is a clique cutset of G, and in this case the theorem holds.
17

Therefore we may assume that S1 ∪ S5 ∪ F = ∅. It follows that V (G) = V1 ∪ V2 ∪ V3 ∪ V4 ∪ V5 ∪ A′ .
Finally, we claim that:
There is an optimal coloring of G in which {v1 , v3 , v5 } is a color class.

(8)

Proof: Let f be any optimal coloring of G, and let c be the color of v3 . If c appears in V1 , then, up
to swapping vertices of V1 , we may assume that c = f (v1 ). If c does not appear in V1 , then, since
N (V1 ) = V2 ∪ A′ ⊂ N (v3 ), color c does not appear in V2 ∪ A′ . Hence we can safely change the color of
v1 to c. We can do the same in V5 concerning v5 . Hence we obtain a coloring of G where {v1 , v3 , v5 } is
a color class, without increasing the number of colors. Thus (8) holds. This completes the proof of the
theorem.

Now we can describe informally our algorithm for coloring (fork, bull)-free graphs. Let G be such a
graph. Using modular decomposition (Theorem 2.2), we may assume that G is prime; and using clique
cutset decomposition (Theorem 2.2), we may assume that G has no clique cutset. If G contains a hole
of length at least 6 (and this can be tested in polynomial time), then by Theorem 6.3, G is either an
odd hole or a bipartite graph, and in the case the solution can be computed directly, as explained above.
Suppose that G contains no hole of length at least 6 and that G contains a P5 (and this can be tested in
time O(|V (G)|5 )). By Theorem 6.5, G we find a stable set S (of size 3) such that χ(G) = χ(G \ S) + 1.
Then we apply recursively the algorithm on G \ S. Finally, suppose that G contains no P5 . Then we can
use the algorithm for the class of (P5 , bull)-free graphs given in the preceding section. Clearly the total
complexity is polynomial.
Acknowledgement. The first author would like to thank Mathew C. Francis for fruitful discussions.
The second and third authors are supported by ANR grant ANR-13-BS02-0007 - STINT.

References
[1] Bodlaender, H. L., Brandstädt,A., Kratsch, D., Rao, M., Spinrad, J. P.: On algorithms for (P5 , gem)-free
graphs. Theoretical Computer Science 349(1), 2-21 (2005).
[2] Brandstädt, A., Le, V. B., Spinrad, J. P.: Graph classes: A survey. SIAM Monographs on Discrete Mathematics, Vol.3, SIAM, Philadelphia (1999).
[3] Broersma, H., Golovach, P., Paulusma, D., Song, J.: Determining the chromatic number of triangle-free
2P3 -free graphs in polynomial time. Theoretical Computer Science 423, 1-10 (2012).
[4] K. Cameron, C.T. Hoàng. Solving the clique cover problem on (bull, C4 )-free graphs. arXiv:1704.00316.
[5] Chudnovsky, M., Cornuejols, G., Liu, X., Seymour, P., Vuskovic, K.: Recognizing berge graphs. Combinatorica 25, 143-186 (2005).
[6] Chudnovsky, M., Seymour, P., Robertson, N., Thomas, R.: The strong perfect graph theorem, Annals of
Mathematics 164(1), 51-229 (2006).
[7] Chvátal, V., Hoàng, C. T., Mahadev, N.V.R., de Werra, D.: Four classes of perfectly orderable graphs.
Journal of Graph Theory 11, 481-495 (1987).
[8] Chvátal, V., Sbihi, N.: Bull-free Berge graphs are perfect. Graphs and Combinatorics 3(1), 127-139 (1987).
[9] Corneil, D., Habib, M., Paul, C., Tedder, M.: Simpler linear-time modular decomposition via recursive
factorizing permutations. Lecture Notes in Computer Science 5125, 634-645 (2008).
[10] Cournier, A., Habib, M.: A new linear algorithm for modular decomposition. Lecture Notes in Computer
Science 787, 68-84 (1994).

18

[11] de Figueiredo, C. M. H., Maffray, F., Porto, O.: On the structure of bull-free perfect graphs. Graphs and
Combinatorics 13(1), 31-55 (1997).
[12] Feige, U., Kilian, J.: Zero knowledge and chromatic number. Journal of Computer and System Sciences 57,
187-199 (1998).
[13] Garey, M. R., Johnson, D. S.: Computers and intractability-A guide to the theory of N P -completeness.
Freeman, San Francisco (1979).
[14] Golovach, P., Johnson, M., Paulusma, D., Song, J.: A survey on the computational complexity of coloring
graphs with forbidden gubgraphs. Journal of Graph Theory 84(4), 331-363 (2017).
[15] Grötschel, M., Lovász, L., Schrijver, A.: Polynomial algorithms for perfect graphs, Annals of Discrete Mathematics 21, 413-441 (1984).
[16] Hoáng, C.T., Kamiński, M., Lozin, V.V., Sawada, J., Shu, X.: Deciding k-colorability of P5 -free graphs in
polynomial time. Algorithmica 57, 74-81 (2010).
[17] Hoáng, C. T., Lazzarato, D.: Polynomial-time alogorithms for minimum weighted colorings of (P5 , P5 )-free
graphs and similar graph classes, Discrete Applied Mathematics 186, 106-111 (2015).
[18] Huang, S.: Improved complexity results on k-coloring Pt -free graphs. Lecture notes in Computer Science
8087, 551-558 (2013).
[19] Karp, R. M.: Reducibility among combinatorial problems. In: Complexity of Computer Computations
(R.E. Miller and J.W. Thatcher editors), Plenum, New York (1972) 85-103.
[20] Karthick, T., Maffray, F.: Maximum weight independent sets in (S1,1,3 , bull)-free Graphs. In: COCOON
2016, Lecture Notes in Computer Science 9797, 385-392 (2012).
[21] Král, D., Kratochvil, J., Tuza, Z., Woeginger, G.: Complexity of coloring graphs without forbidden induced
subgraphs. Lecture notes in Computer Science 2204, 254-162 (2002).
[22] Lozin, V. V., Malyshev, D.S.: Vertex coloring of graphs with few obstructions, Discrete Appied Mathematics
216, 273-280 (2017).
[23] Lund, C., Yannakakis, M.: On the hardness of approximating minimization problems. Journal of the Association for Computing Machinery 41, 960-981 (1994).
[24] Maffray, F., Pastor, L.: The Maximum Weight Stable Set problem in (P6 , bull)-free graphs. In: WG 2016,
Lecture Notes in Computer Science 9941, 85-96 (2016).
[25] Maffray, F., Preissmann, M.: On the N P -completeness of the k-colorability problem for triangle-free graphs.
Discrete Mathematics 162, 313-317 (1996).
[26] Malyshev, D.S.: Two cases of polynomial-time solvability for the coloring problem, Journal of Combinatorial
Optimization 31, 833-845 (2016).
[27] Malyshev, D.S., Lobanova, O.O.: Two complexity results for the vertex coloring problem, Discrete Applied
Mathematics 219, 158-166 (2017).
[28] McConnell, R.M., Spinrad, J.P.: Modular decomposition and transitive orientation. Discrete Mathematics
201, 189-241 (1999).
[29] Rao, M.: MSOL partitioning problems on graphs of bounded treewidth and clique-width. Theoretical Computer Science 377, 260-267 (2007).
[30] Reed, B.A., Sbihi, N.: Recognizing bull-free perfect graphs. Graphs and Combinatorics 11(2), 171-178 (1995).

19

