Defective Coloring on Classes of Perfect Graphs
Rémy Belmonte1 , Michael Lampis2 , and Valia Mitsou3,?

arXiv:1702.08903v1 [cs.DS] 28 Feb 2017

1

University of Electro-Communications, Chofu, Tokyo, 182-8585, Japan,
remy.belmonte@uec.ac.jp
2
Université Paris-Dauphine, PSL Research University, CNRS, UMR 7243
LAMSADE, 75016, Paris, France, michail.lampis@dauphine.fr
3
Université de Lyon, LIRIS, CNRS, UMR 5205,
Université Lyon 1, 69622, Villeurbanne, Lyon, France, vmitsou@liris.cnrs.fr

Abstract. In Defective Coloring we are given a graph G and two
integers χd , ∆∗ and are asked if we can χd -color G so that the maximum
degree induced by any color class is at most ∆∗ . We show that this natural generalization of Coloring is much harder on several basic graph
classes. In particular, we show that it is NP-hard on split graphs, even
when one of the two parameters χd , ∆∗ is set to the smallest possible
fixed value that does not trivialize the problem (χd = 2 or ∆∗ = 1).
Together with a simple treewidth-based DP algorithm this completely
determines the complexity of the problem also on chordal graphs.
We then consider the case of cographs and show that, somewhat surprisingly, Defective Coloring turns out to be one of the few natural
problems which are NP-hard on this class. We complement this negative
result by showing that Defective Coloring is in P for cographs if either χd or ∆∗ is fixed; that it is in P for trivially perfect graphs; and
that it admits a sub-exponential time algorithm for cographs when both
χd and ∆∗ are unbounded.

1

Introduction

In this paper we study the computational complexity of Defective Coloring, which is also known in the literature as Improper Coloring: given a
graph and two parameters χd , ∆∗ we want to color the graph with χd colors
so that every color class induces a graph with maximum degree at most ∆∗ .
Defective Coloring is a very natural generalization of Graph Coloring,
which corresponds to the case ∆∗ = 0. As a result, since the introduction of
this problem more than thirty years ago [13, 2] a great deal of research effort
has been devoted to its study. Among the topics that have been investigated
are its extremal properties [18, 30, 31, 10, 1, 20], especially on planar graphs and
graphs on surfaces [14, 4, 12, 25], as well as its asymptotic behavior on random
graphs [28, 29]. Lately, the problem has attracted renewed interest due to its
applicability to communication networks, with the coloring of the graph modeling the assignment of frequencies to nodes and ∆∗ representing some amount
?

This work has been supported by the ANR-14-CE25-0006 project of the French
National Research Agency.

of tolerable interference. This has led to the study of the problem on Unit Disk
Graphs [24] as well as various classes of grids [3, 7, 5]. Weighted generalizations
have also been considered [6, 23]. More background can be found in the survey
by Frick [17] or Kang’s PhD thesis [27].
Our main interest in this paper is to study the computational complexity of
Defective Coloring through the lens of structural graph theory, that is, to
investigate the classes of graphs for which the problem becomes tractable. Since
Defective Coloring generalizes Graph Coloring we immediately know
that it is NP-hard already in a number of restricted graph classes and for small
values of χd , ∆∗ . Nevertheless, the fundamental question we would like to pose
is what is the additional complexity brought to this problem by the freedom to
produce a slightly improper coloring. In other words, we ask what are the graph
classes where even though Graph Coloring is easy, Defective Coloring is
still hard (and conversely, what are the classes where both are tractable). Though
some results of this type are already known (for example Cowen et al. [14] prove
that the problem is hard even on planar graphs for χd = 2), this question is not
well-understood. Our focus on this paper is to study Defective Coloring on
subclasses of perfect graphs, which are perhaps the most widely studied class of
graphs where Graph Coloring is in P. The status of the problem appears to
be unknown here, and in fact its complexity on interval and even proper interval
graphs is explicitly posed as an open question in [24].

Chordal graphs
Cographs
NP-hard on Split if χd ≥ 2
NP-hard
Theorem 10
Theorem 2
NP-hard on Split if ∆∗ ≥ 1 In P if χd or ∆∗ is fixed
Theorem 9
Theorems 5,6
4/5
∗
In P if χd , ∆ fixed
Solvable in nO(n )
Theorem 13
Theorem 7
In P on Trivially perfect for any χd , ∆∗
Theorem 4

Perfect

Chordal
Cographs
Split

Interval

Trivially Perfect

Table 1. Summary of results

Our results revolve around two widely studied classes of perfect graphs: split
graphs and cographs. For split graphs we show not only that Defective Coloring is NP-hard, but that it remains NP-hard even if either χd or ∆∗ is a
constant with the smallest possible non-trivial value (χd ≥ 2 or ∆∗ ≥ 1). To
complement these negative results we provide a treewidth-based DP algorithm
which runs in polynomial time if both χd and ∆∗ are constant, not only for
split graphs, but also for chordal graphs. This generalizes a previous algorithm
of Havet et al. [24] on interval graphs.
We then go on to show that Defective Coloring is also NP-hard when
restricted to cographs. We note that this result is somewhat surprising since rel-

atively few natural problems are known to be hard for cographs. We complement
this negative result in several ways. First, we show that Defective Coloring
becomes polynomially solvable on trivially perfect graphs, which form a large
natural subclass of cographs. Second, we show that, unlike the case of split
graphs, Defective Coloring is in P on cographs if either χd or ∆∗ is fixed.
Both of these results are based on dynamic programming algorithms. Finally,
by combining the previous two algorithms with known facts about the relation
between χd and ∆∗ we obtain a sub-exponential time algorithm for Defective
Coloring on cographs. We note that the existence of such an algorithm for split
graphs is ruled out by our reductions, under the Exponential Time Hypothesis.
Table 1 summarizes our results. For the reader’s convenience, it also depicts an
inclusion diagram for the graph classes that we mention.

2

Preliminaries and Definitions

We use standard graph theory terminology, see e.g. [16]. In particular, for a graph
G = (V, E) and u ∈ V we use N (u) to denote the set of neighbors of u, N [u]
denotes N (u) ∪ {u}, and for S ⊆ V we use G[S] to denote the subgraph induced
by the set S. A proper coloring of G with χ colors is a function c : V → {1, . . . , χ}
such that for all i ∈ {1, . . . , χ} the graph G[c−1 (i)] is an independent set. We
will focus on the following generalization of coloring:
Definition 1. If χd , ∆∗ are positive integers then a (χd , ∆∗ )-coloring of a graph
G = (V, E) is a function c : V → {1, . . . , χd } such that for all i ∈ {1, . . . , χd }
the maximum degree of G[c−1 (i)] is at most ∆∗ .
We call the problem of deciding if a graph admits a (χd , ∆∗ )-coloring, for
given parameters χd , ∆∗ , Defective Coloring. For a graph G and a coloring
function c : V → N we say that the deficiency of a vertex u is |N (u) ∩ c−1 (c(u))|,
that is, the number of its neighbors with the same color. The deficiency of a
color class i is defined as the maximum deficiency of any vertex colored with i.
We recall the following basic facts about Defective Coloring:
Lemma 1. ([27]) For any χd , ∆∗ and any graph G = (V, E) with χd · ∆∗ ≥ |V |
we have that G admits a (χd , ∆∗ )-coloring.
Proof. Partition V arbitrarily into χd sets of size at most d|V |/χd e and color each
set
a different color. The maximum deficiency of any vertex is at most
m
l with
|V |
|V |
∗
t
u
χd − 1 ≤ χd ≤ ∆ .
Lemma 2. ([27]) If G admits a (χd , ∆∗ )-coloring then ω(G) ≤ χd · (∆∗ + 1).
Proof. For the sake of contradiction, assume that G has a clique of size χd ·(∆∗ +
1) + 1, then any coloring of G with χd colors must give the same color to strictly
more than ∆∗ + 1 vertices of the clique, which implies that these vertices have
deficiency at least ∆∗ + 1.
t
u

Let us now also give some quick reminders regarding the definitions of the
graph classes we consider in this paper.
A graph G = (V, E) is a split graph if V = K ∪ S where K induces a
clique and S induces an independent set. A graph G is chordal if it does not
contain any induced cycles of length four or more. It is well known that all split
graphs are chordal; furthermore it is known that the class of chordal graphs
contains the class of interval graphs, and that chordal graphs are perfect. For
more information on these standard containments see [11].
A graph is a cograph if it is either a single vertex, or the disjoint union of two
cographs, or the complete join of two cographs [33]. A graph is trivially perfect
if in all induced subgraphs the maximum independent set is equal to the number
of maximum cliques [21]. Trivially perfect graphs are exactly the cographs which
are chordal [34], and hence are a subclass of cographs, which are a subclass of
perfect graphs. We recall that Graph Coloring is polynomial-time solvable in
all the mentioned graph classes, since it is polynomial-time solvable on perfect
graphs [22], though of course for all these classes simpler and more efficient
combinatorial algorithms are known.
We will also use the notion of treewidth for the definition of which we refer
the reader to [9, 15].

3

NP-hardness on Cographs

In this section we establish that Defective Coloring is already NP-hard on
the very restricted class of cographs. To this end, we show a reduction from
4-Partition.
Definition 2. In 4-Partition we are given a set A of 4n elements, a size
function s : A → N+ which assigns a value to each element, and a target integer
B. We are asked if there exists a partition of A into n sets of four elements
(quadruples), such that for each set the sum of its elements is exactly B.
4-Partition has long been known to be strongly NP-hard, that is, NP-hard
even if all values are polynomially bounded in n. In fact, the reduction given in
[19] establishes the following, slightly stronger statement.
Theorem 1. 4-Partition is strongly NP-complete if A is given to us partitioned into four sets of equal size A1 , A2 , A3 , A4 and any valid solution is required
to place exactly one element from each Ai , i ∈ {1, . . . , 4} in each quadruple.
Theorem 2. Defective Coloring is NP-complete even when restricted to
complete k-partite graphs. Therefore, Defective Coloring is NP-complete on
cographs.
Proof. We start our reduction from an instance of 4-Partition where the set
of elements A is partitioned into four equal-size sets as in Theorem 1. We first
transform the instance by altering the sizes of all elements as follows: for each
element x ∈ Ai we set s0 (x) := s(x) + 5i B + 55 n2 B and we also set B 0 :=

P4
B + B · i=1 5i + 4 · 55 n2 B. After this transformation our instance is “ordered”,
in the sense that all elements of Ai+1 have strictly larger size than all elements
of Ai . Furthermore, it is not hard to see that the answer to the problem did not
change, as any quadruple that used one element from each Ai and summed up
to B now sums up to B 0 . In addition, we observe that in the new instance the
condition that exactly one element must be used from each set is imposed by
the element sizes themselves: a quadruple that contains two or more elements
of A4 will have sum strictly more than B 0 , while one containing no elements of
A4 will have sum strictly less than B 0 . Similar reasoning can then be applied
to A3 , A2 . We note that the element sizes now have the extra property that
s0 (x) ∈ (B 0 /4 − 5B 0 /n2 , B 0 /4 + 5B 0 /n2 ).
We now construct an instance of Defective Coloring as follows. We set
∆∗ = B 0 and χd = n. To construct the graph G, for each element x ∈ A2 ∪A3 ∪A4
we create an independent set of s0 (x) new vertices which we will call Vx . For each
element x ∈ A1 we construct two independent sets of s0 (x) new vertices each,
which we will call Vx1 and Vx2 . Finally, we turn the graph into a complete 5npartite graph, that is, we add all possible edges while retaining the property that
all sets Vx and Vxi remain independent.
Let us now argue for the correctness of the reduction. First, suppose that
there exists a solution to our (modified) 4-Partition instance where each quadruple sums to B 0 . Number the quadruples arbitrarily from 1 to n and consider the
i-th quadruple (x1i , x2i , x3i , x4i ) where we assume that for each j ∈ {1, . . . , 4} we
have xji ∈ Aj . Hence, s0 (x1i ) is minimum among the sizes of the elements of the
quadruple. We now use color i for all the vertices of the sets Vxj for j ∈ {2, 3, 4}
i
as well as the sets Vx11 , Vx21 . We continue in this way using a different color for
i
i
each quadruple and thus color the whole graph (since the quadruples use all the
elements of A). We observe that for any color i the vertices with maximum deficiency are those from Vx11 and Vx21 , and all these vertices have deficiency exactly
i

i

x1i + x2i + x3i + x4i = B 0 . Hence, this is a valid solution.
For the converse direction of the reduction, suppose we are given a (χd , ∆∗ )coloring of the graph we constructed. We first need to argue that such a coloring
must have a very special structure. In particular, we will claim that in such a
coloring each independent set Vx or Vxi must be monochromatic. Towards this
end we formulate a number of claims.
Claim. Every color i is used on at most 5B 0 /4 + 25B 0 /n2 vertices.
Proof. We will assume that i is used at least 5B 0 /4 + 25B 0 /n2 + 1 times and
obtain a contradiction. Since the size of the largest independent set Vx is at
most B 0 /4 + 5B 0 /n2 we know that color i must appear in at least six different
independent sets. Among the independent sets in which i appears let Vx be the
one in which it appears the minimum number of times. The deficiency of a vertex
0
0
∗
t
u
colored with i in this set is at least 56 |c−1 (i)| ≥ 25B
24 > B = ∆ .
Because of the previous claim, which states that no color appears too many
times, we can also conclude that no color appears too few times.

Claim. Every color i is used on at least 5B 0 /4 − 50B 0 /n vertices.
Proof. First, note that |V | ≥ 5nB 0 /4 − 25B 0 /n because we have created 5n
independent sets each of which has size more than B 0 /4−5B 0 /n2 . P
By the previous
claim any color j 6= i has |c−1 (j)| ≤ 5B 0 /4+25B 0 /n2 . Therefore j6=i |c−1 (j)| ≤
P
0
25B 0
(n−1)(5B 0 /4+25B 0 /n2 ). We have |c−1 (i)| = |V |− j6=i |c−1 (j)| ≥ 5nB
4 − n −
0

0

25B
(n − 1) 5B
4 − (n − 1) n2 =

5B 0
4

−

50B 0
n

+

25B 0
n2

>

5B 0
4

−

50B 0
n .

t
u

Given the above bounds on the size of each color class we can now conclude
that each color appears in exactly five independent sets Vx .
Claim. For each color i the graph induced by c−1 (i) is complete 5-partite.
Proof. First, observe that by the previous claim, there must exist at least 5 sets
Vx or Vxi that intersect c−1 (i), because |c−1 (i)| ≥ 5B 0 /4−O(B 0 /n) while the size
of each such set is at most B 0 /4 + O(B 0 /n2 ); therefore, the size of any four sets
is strictly smaller than |c−1 (i)| (assuming of course that n is sufficiently large).
Suppose now that c−1 (i) intersects 6 different sets, and consider the independent
set Vx on which color i appears at least once but a minimum number of times.
0
50B 0
A vertex colored i in this set will have deficiency at least 65 ( 5B
4 − n ) =
B0
25B 0
0
24 − O( n ), which is strictly greater than B for sufficiently large n. Hence,
color i appears in exactly 5 independent sets.
t
u
Claim. In any valid solution every maximal independent set of G is monochromatic.
Proof. Consider color i, which by the previous claim appears in exactly 5 independent sets. Suppose that one of these is not monochromatic, say colors i, j
appear in Vx . If i appears in at most |Vx |/2 vertices of Vx then we obtain a
contradiction as follows: the total number of times i is used in the graph is at
0
0
1 B0
5B 0
most |c−1 (i)| ≤ 4( B4 + 5B
n2 ) + 2 ( 4 + n2 ), where the first term uses the general
upper bound on the size of all other independent sets where i appears, and the
0
B0
second term uses the same upper bound on |Vx |. Thus, |c−1 (i)| ≤ 9B
8 + O( n2 )
0
0
50B
which is strictly smaller than 5B
4 − n , the minimum number of times that i
must be used (for sufficiently large n). We thus conclude that i must use strictly
more than half of the vertices of Vx . But then we can repeat the same argument
for color j, which is now the minority color in Vx . Hence we conclude that the
independent sets where i is used are monochromatic.
t
u
We are now ready to complete the converse direction of the reduction. Consider the vertices of c−1 (i), for some color i. By the previous sequence of claims
we know that they appear in and fully cover 5 independent sets Vx or Vxi . We
claim that for each j ∈ {2, 3, 4} any color i is used in exactly one Vx with
x ∈ Aj . This can be seen by considering the deficiency of the vertices of the
smallest independent set where i appears. The deficiency of these vertices is
equal to x1i + x2i + x3i + x4i , which are the sizes of the four larger independent
sets. By the construction of the modified 4-Partition instance, any quadruple

that contains two elements of A4 will have sum strictly greater than B 0 . Hence,
these elements must be evenly partitioned among the color classes, and with
similar reasoning the same follows for the elements of A3 , A2 .
We thus arrive at a situation where each color i appears in the independent
sets Vx4i , Vx3i , Vx2i as well as two of the “small” independent sets. Recall that all
“small” independent sets were constructed in two copies of the same size Vx1 , Vx2 .
We would now like to ensure that all color classes contain one small independent
set of the form Vx11 . If we achieve this the argument will be complete: we construct
i

the quadruple (x4i , x3i , x2i , x1i ) from the color class i, and the deficiency of the
vertices of the remaining small independent set ensures that the sum of the
elements of the quadruple is at most B 0 . By constructing n such quadruples we
conclude that they all have sum exactly B 0 , since the sum of all elements of the
4-Partition instance is (without loss of generality) exactly nB 0 .
To ensure that each color class contains an independent set Vx1 we first observe that we can always exchange the colors of independent sets Vx1 and Vx2 ,
since they are both of equal size (and monochromatic). Construct now an auxiliary graph with χd vertices, one for each color class and a directed edge for each
x ∈ A1 . Specifically, if for x ∈ A1 the independent set Vx1 is colored i and the
set Vx2 is colored j we place a directed edge from i to j (note that this does not
rule out the possibility of self-loops). In the auxiliary graph, each vertex that
does not have a self-loop is incident on two directed edges. We would like all
such vertices to end up having out-degree 1, because then each color class would
contain an independent set of the form Vx1 . The main observation now is that
in each weakly connected component that contains a vertex u with out-degree 0
there must also exist a vertex v of out-degree 2. Exchanging the colors of Vx1 and
Vx2 corresponds to flipping the direction of an edge in the auxiliary graph. Hence,
we can take a maximal directed path starting at v and flip all its edges, while
maintaining a valid coloring of the original graph. This decreases the number
of vertices with out-degree 0 and therefore repeating this process completes the
proof.
t
u

4

Polynomial time algorithm on trivially perfect graphs

In this section, we show that the NP-completeness proof from Section 3 is essentially tight by giving a polynomial time algorithms for Defective Coloring on
the class of trivially perfect graphs. We will heavily rely on the following equivalent characterization of trivially perfect graphs given by Golumbic [21]:
Theorem 3. A graph is trivially perfect if and only if it is the comparability
graph of a rooted tree.
In other words, for every trivially perfect graph G, there exists a rooted tree
T such that making every vertex in the tree adjacent to all of its descendants
yields a graph isomorphic to G. We refer to T as the underlying rooted tree of
G. We recall that it is known how to obtain T from G in polynomial (in fact
linear) time [34].

We are now ready to describe our algorithm. The following observation is
one of its basic building blocks.
Lemma 3. Let G = (V, E) be a trivially perfect graph, T its underlying rooted
tree, and u ∈ V be an ancestor of v ∈ V in T . Then N [v] ⊆ N [u].
Proof. Any vertex w ∈ N [v] must be either a descendant of v, in which case it is
also a descendant of u and w ∈ N [u], or another ancestor of v. However, because
T is a tree, if w is an ancestor of v, then w is either an ancestor or a descendant
of u.
t
u
Theorem 4. Defective Coloring can be solved in polynomial time on trivially perfect graphs.
Proof. Given a trivially perfect graph G = (V, E) with underlying rooted tree
T = (V, E 0 ) and two non-negative integers χd and ∆∗ , we compute a coloring
of G using at most χd colors and with deficiency at most ∆∗ as follows. First,
we partition the vertices of T (and therefore of G) into sets V1 , . . . , V` , where
` denotes the height of T , such that V1Scontains the leaves of T and, for every
i−1
2 ≤ i ≤ `, Vi contains the leaves of T \ ( j=1 Vj ). Observe that each set Vi is an
independent set in G. We now start our coloring by giving all vertices of V1 color
1. Then, for every 2 ≤ i ≤ `, we color the vertices of Vi by giving each of them
the lowest color available, i.e., we color each vertex u with the lowest j such that
u has at most ∆∗ descendants colored j. If for some vertex no color is available,
that is, its subtree contains at least ∆∗ + 1 vertices colored with each of the
colors {1, . . . , χd }, then we return that G does not admit a (χd , ∆∗ )-coloring.
This procedure can clearly be performed in polynomial time and, if it returns
a solution, it uses at most χd colors. Furthermore, whenever the procedure uses
color i on a vertex u it is guaranteed that u has deficiency at most ∆∗ among
currently colored vertices. Because any neighbor of u that is currently colored
with i must be a descendant of u, by Lemma 3 this guarantees that the deficiency
of all vertices remains at most ∆∗ at all times.
It now only remains to prove that the algorithm concludes that G cannot be
colored with χd colors and deficiency ∆∗ only when no such coloring exists. For
this we will rely on the following claim which states that any valid coloring can
be “sorted”.
Claim. If G admits a (χd , ∆∗ )-coloring, then there exists a (χd , ∆∗ )-coloring of
G c such that, for every two vertices u, v ∈ V (G), if v is a descendant of u, then
c(v) ≤ c(u).
Proof. Let us consider an arbitrary (χd , ∆∗ )-coloring c∗ : V (G) → {1, . . . , c}
of G. We describe a process which, as long as there exist u, v ∈ V with u an
ancestor of v and c(u) < c(v) transforms c∗ to another valid coloring which is
closer to having the desired property. So, suppose that such a pair u, v exists,
and furthermore, if many such pairs exist, suppose that we select a pair where
u is as close to the root of T as possible. As a result, we can assume that no

ancestor u0 of u has color c∗ (u), because otherwise we would have started with
the pair u0 , v.
We will now consider two cases. Assume first that there exists a vertex x
such that c∗ (x) = c∗ (v) and x is an ancestor of u. We claim that swapping the
colors of u and v yields a new coloring of G with deficiency at most ∆∗ . The only
affected vertices are those colored c∗ (u) or c∗ (v). Regarding color c∗ (u), because
by Lemma 3 N [v] ⊆ N [u] and color c∗ (u) was moved from u to v, the deficiency
of every vertex colored c∗ (u) in V \ {u, v} is at most as high as it was before,
and the deficiency of v is at most as high as the deficiency of u in c∗ . Regarding
color c∗ (v) we observe that the deficiency of vertex x remains unchanged, since
both u, v are its neighbors, and the same is true for all ancestors of x. Since the
deficiency of x is at most ∆∗ , by Lemma 3, the deficiency of every descendant
of x colored with c∗ (v) is also at most ∆∗ .
For the remaining case, suppose that no ancestor of u uses color c∗ (v). Recall
that we have also assumed that no ancestor of u uses color c∗ (u). We therefore
transform the coloring as follows: in the subtree rooted at u we exchange colors
c∗ (u) and c∗ (v) (that is, we color all vertices currently colored with c∗ (u) with
c∗ (v) and vice-versa). Because no ancestor of u uses either of these two colors,
this exchange does not affect the deficiency of any vertex.
We can now repeat this procedure as follows: as long as there is a conflicting
pair u, v, with u an ancestor of v and c∗ (u) < c∗ (v) we select such a pair with u as
close to the root as possible and, if there are several such pairs, we select the one
with maximum c∗ (v). We perform the transformation explained above on this
pair and then repeat. It is not hard to see that every vertex will be used at most
once as the ancestor u in this transformation, becuase after the transformation
it will have the highest color in its subtree. Hence we will eventually obtain the
claimed property.
t
u
It follows from the previous claim that if a (χd , ∆∗ )-coloring exists, then a
sorted coloring (χd , ∆∗ )-coloring exists where ancestors always have colors at
least as high as their descendants. We can now argue that our algorithm also
produces a sorted coloring, with the extra property that whenever it sets c(u) = i
we know that any sorted (χd , ∆∗ )-coloring of G must give color at least i to u.
This can be shown by induction on i: it is clear for the vertices of V1 to which
the algorithm gives color 1; and if the algorithm assigns color i to u, then u has
∆∗ + 1 descendants which (by inductive hypothesis) must have color at least
i − 1 in any valid sorted coloring of G.
t
u

5

Algorithms on Cographs

In this section we present algorithms that can solve Defective Coloring on
cographs in polynomial time if either ∆∗ or χd is bounded; both algorithms rely
on dynamic programming. After presenting them we explain how their combination can be used to obtain a sub-exponential time algorithm for Defective
Coloring on cographs.

5.1

Algorithm for Small Deficiency

We now present an algorith that solves Defective Coloring in polynomial
time on cographs if ∆∗ is bounded. Before we proceed, let us sketch the main
ideas behind the algorithm. Given a (χd , ∆∗ )-coloring c of a graph G, we define the type of a color class i, as the pair of two integers (si , di ) where si :=
min{|c−1 (i)|, ∆∗ +1} and di is the maximum degree of G[c−1 (i)]. In other words,
the type of a color class is characterized by its size (up to value ∆∗ + 1) and
the maximum deficiency of any of its vertices. We observe that there are fewer
than (∆∗ + 1)2 possible types in a valid (χd , ∆∗ )-coloring, because si only takes
values in {1, . . . , ∆∗ + 1} and di in {0, . . . , ∆∗ }.
We can now define the signature of a coloring c as a tuple which contains one
element for every possible color type (s, d). This element is the number of color
classes in c that have type (s, d), and hence is a number in {0, . . . , χd }. We can
∗
2
conclude that there are at most (χd + 1)(∆ +1) possible signatures that a valid
∗
(χd , ∆ )-coloring can have. Our algorithm will maintain a binary table which
states for each possible signature if the current graph admits a (χd , ∆∗ )-coloring
with this signature. The obstacle now is to describe a procedure which, given
two such tables for graphs G1 , G2 is able to generate the table of admissible
signatures for their union and their join.
∗
Theorem 5. Thereis an algorithm
 which decides if a cograph admits a (χd , ∆ )∗
O((∆∗ )4 )
coloring in time O χd
.

Proof. We use the ideas sketched above. Specifically, we say that a coloring
signature S is a function {1, . . . , ∆∗ + 1} × {0, . . . , ∆∗ } → {0, . . . , χd } and a
coloring c has signature S if for any (s, d) ∈ {1, . . . , ∆∗ + 1} × {0, . . . , ∆∗ } the
number of color classes with type (s, d) in c is S((s, d)). Our algorithm will
maintain a binary table T with the property that, for S a possible coloring
signature we have T (S) = 1 if and only if there exists a (χd , ∆∗ )-coloring of G
∗
2
with signature S. The size of T is therefore at most (χd + 1)(∆ +1) .
It is not hard to see how to compute T if G consists of a single vertex: the
only color class then has type (1, 0), so the only possible signature is the one
that sets S((1, 0)) = 1 and S((s, d)) = 0 otherwise.
Now, suppose that G is either the union or the join of two graphs G1 , G2 for
which our algorithm has already calculated the corresponding tables T1 , T2 . We
will use the fact that for any valid (χd , ∆∗ )-coloring c of G with signature S, its
restrictions to G1 , G2 are also valid (χd , ∆∗ )-colorings. If these restrictions have
signatures S1 , S2 it must then be the case that T1 (S1 ) = T2 (S2 ) = 1. It follows
that in order to compute all the signatures for which we must have T (S) = 1 it
suffices to consider all pairs of signatures S1 , S2 such that T1 (S1 ) = T2 (S2 ) = 1
and decide if it is possible to have a coloring of G with signature S whose
restrictions to G1 , G2 have signatures S1 , S2 .
Given two signatures S1 , S2 such that T1 (S1 ) = T2 (S2 ) = 1 we would therefore like to generate all possible signatures S for colorings c of G such that S1 , S2
represent the restriction of c to G1 , G2 . Every color class of c will either consist

of vertices of only one subgraph G1 or G2 , or it will be the result of merging
a color class of G1 with a color class of G2 . Our algorithm will enumerate all
possible merging combinations between color classes of G1 and G2 .
Let us now explain how we enumerate all merging possibilities. Let c1 , c2 be
(χd , ∆∗ )-colorings of G1 , G2 with signatures S1 , S2 respectively. If G is the join
of G1 , G2 we say that type (s1 , d1 ) is mergeable with type (s2 , d2 ) if s1 +d2 ≤ ∆∗
and s2 + d1 ≤ ∆∗ . If G is the union of G1 , G2 we say that any pair of types is
mergeable. Furthermore, if G is the join of G1 , G2 and (s1 , d1 ), (s2 , d2 ) are mergeable types, we say that they merge into type (min{s1 + s2 , ∆∗ + 1}, max{d1 +
s2 , d2 + s1 }). If G is the union of G1 , G2 we say that types (s1 , d1 ) and (s2 , d2 )
merge into type (min{s1 + s2 , ∆∗ + 1}, max{d1 , d2 }). The intuition behind these
definitions is that a color class i of c1 is mergeable with a color class j of c2 if
−1
we can use a single color for c−1
1 (i) ∪ c2 (j) in G, and the type of this color class
is the type into which the types of i, j merge.
We now construct a bipartite graph G0 (A1 , A2 , E 0 ) that will help us enumerate all merging combinations. The graph consists of (∆∗ + 1)2 vertices on each
side, each corresponding to a type. We place an edge between two vertices if
their corresponding types are mergeable (so if G is a union of G1 , G2 then G0 is
a complete bipartite graph). We also give a weight to each vertex as follows: if
u ∈ Ai corresponds to type (s, d) we set w(u) = Si ((s, d)). In words, the weight
of a vertex that represents a type is the number of color classes of that type in
the coloring of the subgraphs.
We will now enumerate all weighted matchings of G0 , where a weighted
matchingP
is an assignment of weights to E 0 such that for all vertices u ∈ A1 ∪ A2
we have v∈N (u) w((u, v)) ≤ w(u). It is not hard to see that the total number
∗

4

of valid weighted matchings is at most (χd + 1)(∆ +1) , since every edge must
receive in weight {0, . . . , χd } and there are at most (∆∗ + 1)4 edges. This is the
step that dominates the running time of our algorithm.
For each of the enumerated matchings of G0 we can now calculate a signature
S of a coloring of G. For each type (s, d) let E(s,d) ⊆ E 0 be the set of edges of G0
whose endpoints merge into type (s, d). Let
vertices correspondP ui ∈ Ai be theP
ing to type (s, d). We have S((s, d)) =
(w(ui ) − v∈N (ui ) w(ui , v)) +
i=1,2
P
e∈E(s,d) w(e). We now check that the signature we computed refers to a colorP
ing with at most χd colors, that is, if S((s, d)) ≤ χd , where s ∈ {1, . . . , ∆∗ +1}
and d ∈ {0, . . . , ∆∗ }. In this case we set T (S) = 1. The observation that completes the proof is that for all valid colorings c of G with signature S such that
the restriction of c to G1 , G2 has signatures S1 , S2 there must exist a weighted
matching for which the above procedure finds the signature S. Hence, by examining all pairs of feasible signatures S1 , S2 we will discover all feasible signatures
of G.
t
u
5.2

Algorithm for Few Colors

In this section we provide an algorithm that solves Defective Coloring in
polynomial time on cographs if χd is bounded. The type of a color class i

is defined in a similar manner as in the first paragraph of Section 5.1, with
the only difference that the first coordinate of the output pair takes values
in {0, . . . , ∆∗ + 1}. The signature S of a coloring c is now a function S :
{1, . . . , χd } → {0, . . . , ∆∗ + 1} × {0, . . . , ∆∗ }, which takes as input a color class
and returns its type. Once again, we should maintain a table T of size less than
(∆∗ + 2)2χd for which T (S) = 1 if and only if there is a (χd , ∆∗ )-coloring of
signature S for the current graph G. As in the previous section, we shall describe how to compute table T of a graph G which is the union or the join of
two graphs G1 and G2 whose tables T1 and T2 are known.
Theorem 6. There is an algorithm which decides if a cograph admits a (χd , ∆∗ )coloring O∗ (∆∗ )O(χd ) .
Proof. The base case is when we introduce a single vertex u to the graph G. In
this case, any coloring of u is valid, so for all i ∈ {1, . . . , χd } we define a signature
Si such that Si (i) = (1, 0) and Si (j) = (0, 0) when i 6= j. Last, T (S) = 1 if and
only if S = Si for any i.
Now, suppose that G is either the union or the join of two graphs G1 , G2 for
which we have already calculated their corresponding tables. Once again we just
need to consider all pairs of signatures S1 , S2 such that T1 (S1 ) = T2 (S2 ) = 1
and decide if we can have a coloring of G with signature S whose restrictions to
G1 , G2 have signatures S1 , S2 . Let S1 , S2 be one such pair of signatures, for which
Sj (i) = (sij , dij ), j = 1, 2. We examine the cases of union and join separately.
Let us start with the case that G is the union of G1 , G2 . Define S such that
for any i, S(i) = (min{si1 + si2 , ∆∗ + 1}, max{di1 , di2 }) and set T (S) = 1.
The case where G is the join of G1 , G2 is a little more complicated since we
first need to check if, given two precolored graphs the outcome of their join is
valid, that for all colors i, the maximum degree of G[i] remains at most ∆∗ . This
corresponds to checking for all colors i whether d = max{si1 + di2 , si2 + dj1 } ≤ ∆∗ .
Given that the above is true, we define S such that for any i, S(i) = (min{si1 +
si2 , ∆∗ + 1}, d) and set S(T ) = 1.
The algorithm considers all pairs
 of elements of T1 , T2 , so it runs in time
dominated by |Ti |2 = O∗ (∆∗ )O(χd ) .
t
u
5.3

Sub-Exponential Time Algorithm

Finally, in this section we combine the algorithms of Sections 5.1 and 5.2 in order
to obtain a sub-exponential time algorithm for cographs.
Theorem 7. Defective Coloring can be solved in time n

 4 
O n /5

on cographs.

Proof. First, we remind the reader that, from Lemma 1, if ∆∗ · χd ≥ n then the
answer is trivially yes. Thus the interesting case is when ∆∗ · χd < n. Note that
we also trivially have that ∆∗ , χd ≤ n.


√
∗ 4
If ∆∗ ≤ 5 n, then the algorithm of Section 5.1 runs in O∗ χd O((∆ ) ) =
 4 
O n /5

n

time.

If ∆∗ >
runs in O∗

6

√
5

4

n, then χd < n/∆∗ < n 5 . In this case, the algorithm of Section 5.2
4

O n /5
(∆∗ )O(χd ) = n
time.
t
u

Split and Chordal Graphs

In this section we present the following results: first, we show that Defective
Coloring is hard on split graphs even when ∆∗ is a fixed constant, as long as
∆∗ ≥ 1; the problem is of course in P if ∆∗ = 0. Then, we show that Defective
Coloring is hard on split graphs even when χd is a fixed constant, as long as
χd ≥ 2; the problem is of course trivial if χd = 1. These results completely
describe the complexity of the problem when one of the two relevant parameters
is fixed. We then give a treewidth-based procedure through which we obtain
a polynomial-time algorithm even on chordal graphs when χd , ∆∗ are bounded
(in fact, the algorithm is FPT parameterized by χd + ∆∗ ). Hence these results
give a complete picture of the complexity of the problem on chordal graphs: the
problem is still hard when one of χd , ∆∗ is bounded, but becomes easy if both
are bounded.
Let us also remark that both of the reductions we present are linear. Hence,
under the Exponential Time Hypothesis [26], they establish not only NP-hardness,
but also unsolvability in time 2o(n) for Defective Coloring on split graphs,
for constant values of χd or ∆∗ . This is in contrast with the results of Section
5.3 on cographs.
6.1

Hardness for Bounded Deficiency

In this section we show that Defective Coloring is NP-hard for any fixed
value ∆∗ ≥ 1. We first show hardness for ∆∗ = 1, then we tweak our reduction
in order to make it work for larger ∆∗ .
We will reduce from 3CNFSAT. Suppose we are given a CNF formula f where
X = {x1 , . . . , xn } are the variables and C = {c1 , . . . , cm } are the clauses and
each clause contains exactly 3 literals. We construct a split graph G = (V, E),
where {U, Z} is a partition of V with U inducing a clique of 4n vertices and Z
inducing an independent set of m + 4n vertices, such that having a satisfying
assignment s : X → {T, F } for f implies a (2n, 1)-coloring c : V → {1, . . . , 2n}
for G and vice versa.
The construction is as follows. For every variable xi , i ∈ {1, . . . , n} we conB
C
D
struct a set of four vertices Ui = {uA
i , ui , ui , ui } which should be part of the
clique vertices U (that is, for all i ∈ {1, . . . , n} and k ∈ {A, B, C, D}, vertices uki
are fully connected). We also construct four vertices Zi = {ziA , ziB , ziC , ziD } in the
independent set Z. Furthermore, for each clause cj , j ∈ {1, . . . , m} we construct
a vertex vj in the independent set. Last we add every edge between U and Z save
for the following non-edges: for every i ∈ {1, . . . , n}, k ∈ {A, B, C, D}, zik does
0
not connect to vertices uki , k 0 6= k and for every i ∈ {1, . . . , n}, j ∈ {1, . . . , m},
if clause cj contains variable xi then: if xi appears positive then vj does not

B
connect to uA
i , ui , whereas if it appears negative then vj does not connect to
C
A
ui , ui . This completes the construction.

Lemma 4. Given a satisfying assignment s : X → {T, F } for f we can always
construct a (2n, 1)-coloring c : V → {1, . . . , 2n}.
Proof. Let us first assign colors to the clique vertices. We are going to use two
distinct colors for every quadruple Ui . The way we choose to color vertices in
B
Ui should depend on the assignment s(xi ): if s(xi ) = T then c(uA
i ) = c(ui ) =
C
D
A
C
2i − 1 and c(ui ) = c(ui ) = 2i; if s(x) = F then c(ui ) = c(ui ) = 2i − i and
D
c(uB
i ) = c(ui ) = 2i. Observe that we have consumed the entire supply of the 2n
available colors on coloring U and for every color l ∈ {1, . . . , 2n} we have that
|c−1 (l) ∩ U | = 2.
In order to finish coloring the independent set Z, we can only reuse colors
that have already appeared in U . If for some z ∈ Z there exists a color l such
that c−1 (l)∩N (z) = ∅, that is if both vertices of color l in U are non-neighbors of
z, then we can assign c(z) = l. Remember that a vertex in Zi is a non-neighbor
of exactly three vertices in Ui , thus two of them should be using the same color.
Additionally, if s is a satisfying assignment for f , then for every cj there is
at least one satisfied literal, say (¬)xi and by the construction of G and the
assignment of colors on U we should be able once again to find two vertices in
Ui having the same color that vj does not connect to, these should be uA
i and,
C
depending on s, either uB
t
u
i or ui .
Lemma 5. Given a (2n, 1)-coloring c : V → {1, . . . , 2n} of G, we can produce
a satisfying assignment s : X → {T, F } for f .
Proof. First, observe that, since ∆∗ = 1, for any color l ∈ {1, . . . , 2n} we have
that |c−1 (l) ∩ U | ≤ 2. Since there are at most 2n colors in use and |U | = 4n,
that means that the color classes of c should induce a matching of size 2n in the
clique. The above imply that for any z ∈ Z with c(z) = l there exist u, u0 ∈ U
with c(u) = c(u0 ) = l which are non-neighbors of z.
We can now make the following claim:
Claim. For any u, u0 ∈ U , if c(u) = c(u0 ) then there exists i such that u, u0 ∈ Ui .
Proof. This is a consequence of vertices in Zi having exactly three non-neighbors
in U all of them belonging to Ui . More precisely, for any k ∈ {A, B, C, D},
c(zik ) = l for some color l implies that ∃k1 , k2 6= k such that c(uki 1 ) = c(uki 2 )(= l).
Similarly, the fact that c(zik1 ) = l0 for some color l0 together with the fact that
0
0
|c−1 (l) ∩ U | = 2 gives us that c(uki ) = c(uki )(= l0 ), where of course uki , uki are
0
the only vertices of U colored l .
t
u
B
The above claim directly provides the assignment: if c(uA
i ) = c(ui ) then set
s(xi ) = T , else s(xi ) = F .

Claim. The assignment s as described above satisfies f .

Proof. By construction, for all j ∈ {1, . . . , m}, vertex vj should be a nonneighbor to six vertices of U . At least two of them, call them u, u0 should have
the same color as vj . From the previous claim, u, u0 should belong to the same
0
B
C
0
B
group Ui . By construction u = uA
i and u ∈ {ui , ui }. Consider that u = ui
0
C
A
B
(similar arguments hold when u = ui ). Since c(ui ) = c(ui ), the assignment
should set s(xi ) = T . Observe now that cj , which by construction contains literal
xi , should be satisfied.
t
u
This concludes the proof.

t
u

Lemmata 4, 5 prove the following Theorem:
Theorem 8. Defective Coloring is NP-hard on split graphs for ∆∗ = 1.
To show hardness for ∆∗ ≥ 2, all we need to do is slightly change the above
construction so that we are now forced to create bigger color classes. Namely,
we add 2(∆∗ − 1)n more vertices to U which we divide into 2n sets UiD and UiA
and which we fully connect to each other and to previous vertices of U . We also
remove vertices ziB , ziC from Zi . Last, for k ∈ {A, D}, we connect vertices of Uik
to all vertices in Z save for the following: UiD does not connect to ziA and UiA
does not connect to ziD and to vj if variable xi appears in clause cj .
Lemma 6. Given a satisfying assignment s for f we can always construct a
(2n, ∆∗ )-coloring c.
Proof. The assignment of colors on old vertices remains the same; for u ∈ UiD
set c(u) = 2i, whereas for u ∈ UiA , set c(u) = 2i − 1. Again, having a satisfying
assignment for f means that literal (¬)xi which appears in cj is set to true by
s, so with similar arguments as above we can set c(vj ) = 2i − 1.
t
u
Lemma 7. Given a (2n, ∆∗ )-coloring c, we can produce a satisfying assignment
s for f .
Proof. For the other direction, as in the case ∆∗ = 1, we can derive now that
for any color l, |c−1 (l) ∩ U | = ∆∗ + 1. Having c(ziD ) = l for some color l means
B
C
that at least ∆∗ + 1 vertices among UiA ∪ {uA
i , ui , ui } also have color l, where
A
A
B
C
∗
|Ui ∪ {ui , ui , ui }| = ∆ + 2. This implies the following two properties:
B
C
Property 1. ∀u, c(u) = l implies u ∈ UiA ∪ {uA
i , ui , ui }.
A
B
C
Property 2. At least two vertices out of {ui , ui , ui } have color l.
C
Claim. c(uB
i ) 6= c(ui )

Proof. Since c(ziA ) = l0 for some color l0 , that means that at least ∆∗ + 1 vertices
C
D
0
−1 0
among UiD ∪{uB
(l )∩
i , ui , ui } are given the same color l . Observe that ∃u ∈ c
D
D
0
B
C
(Ui ∪{ui }) and from Property 1, l 6= l. Assuming c(ui ) = c(ui ) implies l = l0 ,
a contrudiction.
t
u

B
Thus, from Property 2 and the above claim, either UiA ∪ {uA
i , ui } have the
C
A
0
A
D
C
D
same color l (and Ui ∪ {ui , ui } have color l ) or Ui ∪ {ui , ui } have color l
D
0
(and UiD ∪ {uB
i , ui } have color l ). The assignment again depends on whether
A
B
c(ui ) = c(ui ) and the correctness follows similar ideas to the case ∆∗ = 1. t
u

The main theorem of this section follows from Lemmata 6,7 and Theorem 8.
Theorem 9. Defective Coloring is NP-hard on split graphs for any fixed
∆∗ ≥ 1.
6.2

Hardness for Bounded Number of Colors

Theorem 10. Defective Coloring is NP-complete on split graphs for every
fixed value of χd ≥ 2.
Proof. We reduce from the problem 3-Set Splitting, which takes as input
a set of elements U , called the universe, and a family F of subsets of U of
size exactly 3, and asks whether there is a partition (U1 , U2 ) of U such that,
for every set S ∈ F, we have S ∩ U1 6= ∅ and S ∩ U2 6= ∅. This problem is
well-known to be NP-complete [19]. Given an instance (U, F) of 3-Set Splitting and a positive integer χd , we build a split graph G = (V, E) such that
V = C1 ∪ C2 ∪ C ∗ ∪ I ∪ Z1 ∪ Z2 , with |C1 | = |C2 | = |F|, |C ∗ | = (χd − 2) · (|F| + 2),
|I| = |U | and |Z1 | = |Z2 | = χd · (|F| + 2). We proceed by making all the vertices
of C1 ∪C2 pairwise adjacent. We then associate each set S of F with two vertices
vS1 and vS2 of C1 and C2 respectively, and every element x of U with a vertex
wx of I. For every pair x ∈ U, S ∈ F, we make wx adjacent to vS1 and vS2 if
and only if x ∈ S. We complete our construction by making all the vertices of
Ci adjacent to all the vertices of Zi for i ∈ {1, 2}, and all the vertices of C ∗
adjacent to every other vertex in V . Observe that the graph we constructed is
split, since C1 ∪ C2 ∪ C ∗ induces a clique and I ∪ Z1 ∪ Z2 induces an independent
set. We now claim that there exists a partition (U1 , U2 ) of U as described above
if and only if G can be colored with at most χd colors and deficiency at most
∆∗ = |F| + 1.
For the forward direction, it suffices to observe that coloring every vertex
of C1 ∪ Z2 ∪ U1 with color 1, every vertex of C2 ∪ Z1 ∪ U2 with color 2, and
coloring the vertices of C ∗ equitably with the remaining χd − 2 colors produces
the desired coloring of G.
For the converse, we first prove the following:
Claim. For any coloring of G with χd colors and deficiency at most ∆∗ , all the
vertices of C1 have the same color. Similarly, all the vertices of C2 have the same
color, and this color is distinct from that of the vertices of C1 . Additionally, the
remaining χd − 2 colors are each used exactly ∆∗ + 1 times in C ∗ .

Proof. We first consider the colors given to the vertices of Z1 and Z2 . Observe
that since both sets have size χd · (|F| + 2) = χd · (∆∗ + 1), there is a color c1
that appears at least ∆∗ + 1 times in Z1 and a color c2 that appears at least
∆∗ + 1 times in Z2 . Since Z1 ⊂ N (u) for every vertex u ∈ C1 ∪ C ∗ , we obtain
that no vertex of C1 ∪ C ∗ uses color c1 . Using a similar argument, we obtain
that no vertex of C2 ∪ C ∗ uses color c2 .
We will first prove that c1 6= c2 . Indeed, suppose that c1 = c2 . Since this
color c1 does not appear in C1 ∪ C2 ∪ C ∗ , we are left with χd − 1 available colors
for these sets, where |C1 ∪C2 ∪C ∗ | = χd ·|F|+2χd −4. To obtain a contradiction
∗
2 ∪C |
> |F +2|
observe that at least one color class should have size at least |C1 ∪C
χd −1
for sufficiently large F, which is more than ∆∗ + 1 vertices.
The above implies that C ∗ must be colored using at most χd − 2 colors. Since
∗
C is a clique of size exactly (χd − 2) · (|F| + 2) = (χd − 2) · (∆∗ + 1), it follows
that C ∗ is colored using χd − 2 colors, each of which are used exactly ∆∗ + 1
times, as desired. Last, we conclude that vertices in C1 should only be colored
c2 and similarly vertices of C2 should receive color c1 .
t
u
By the previous claim C1 and C2 are both monochromatic and use different
colors. Without loss of generality suppose that C1 is colored with color 1 and
C2 with color 2. Since every vertex of I is adjacent to every vertex of C ∗ , we
immediately obtain that I must be colored using only 1 or 2. It only remains to
show that for every set S of F, there exist elements x, y ∈ S such that vertex wx
is colored with color 1 and vertex wy is colored with color 2. Then, the coloring
of I will give us a partition of U . Assume for contradiction that there exists a
set S whose elements x, y and z all have the same color, say color 1. From the
above claim, we know that vS1 ∈ C1 uses color 1 and is adjacent to the other
∆∗ − 2 vertices of C1 , all of which also use color 1. Therefore, vS1 is adjacent to
∆∗ −2+3 vertices using color 1, and hence has deficiency ∆∗ +1, a contradiction.
This concludes the proof.
t
u
6.3

A Dynamic Programming Algorithm

In this section we present an algorithm which solves the problem efficiently on
chordal graphs when χd and ∆∗ are small. Our main tool is a treewidth-based
procedure, as well as known connections between the maximum clique size and
treewidth of chordal graphs.
Theorem 11. Defective Coloring can be solved in time (χd ∆∗ )O(tw) nO(1)
on any graph G with n vertices if a tree decomposition of width tw of G is supplied
with the input.
Proof. We describe a dynamic programming algorithm which uses standard techniques, and hence we sketch some of the details. Suppose that we are given a
rooted nice tree decomposition of G (we use here the definition of nice tree decomposition given in [9]). For every bag B of the decomposition we denote by B ↓
the set of vertices of G that appear in B and bags below it in the decomposition.

For a coloring c : V → {1, . . . , χd } we say that the partial type of a vertex u ∈ B
is a pair consisting of c(u) and |c−1 (c(u)) ∩ N (u) ∩ B ↓ |. In words, the type of a
vertex is its color and its deficiency in the graph induced by B ↓ . Clearly, if c is
a valid coloring, any vertex can have at most χd · (∆∗ + 1) types. Hence, if we
define the type of B as a tuple containing the types of its vertices, any bag can
have one of at most (χd · (∆∗ + 1))tw types.
Our dynamic programming algorithm will now construct a table which for
every bag B and every possible bag type decides if there is a coloring of B ↓
with the specified type for which all vertices of B ↓ \ B have deficiency at most
∆∗ . The table is easy to construct for leaf bags and forget bags. For introduce
bags we consider all possible colors of the new vertex, and for each color we
appropriately compute its deficiency and update the deficiency of its neighbors
in the bag, rejecting solutions where a vertex reaches deficiency ∆∗ + 1. Finally,
for join bags we consider any pair of partial solutions from the two children bags
that agree on the colors of all vertices of the bag and compute the deficiency of
each vertex as the sum of its deficiencies in the two solutions.
t
u
We now recall the following theorem connecting ω(G) and tw(G) for chordal
graphs.
Theorem 12. ([32, 8]) In chordal graphs ω(G) = tw(G) + 1. Furthermore, an
optimal tree decomposition of a chordal graph can be computed in polynomial
time.
Together with Lemma 2 this gives the following algorithm for chordal graphs.
∗

Theorem 13. Defective Coloring can be solved in time (χd ∆∗ )O(χd ∆ ) nO(1)
in chordal graphs.
Proof. We use Theorem 12 to compute an optimal tree decomposition of the
input graph and its maximum clique size. If ω(G) > χd (∆∗ + 1) then we can
immediately reject by Lemma 2. Otherwise, we know that tw(G) ≤ χd (∆∗ + 1)
from Theorem 12, so we apply the algorithm of Theorem 11.
t
u

7

Conclusions

Our results indicate that Defective Coloring is significantly harder than
Graph Coloring, even on classes where the latter is easily in P. Though we
have completely characterized the complexity of the problem on split and chordal
graphs, its tractability on interval and proper interval graphs remains an interesting open problem as already posed in [24].
Beyond this, the results of this paper point to several potential future directions. First, the algorithms we have given for cographs are both XP parameterized by χd or ∆∗ . Is it possible to obtain FPT algorithms? On a related question,
is it possible to obtain a faster sub-exponential time algorithm for Defective
Coloring on cographs? Second, is it possible to find other natural classes of
graphs, beyond trivially perfect graphs, which are structured enough to make

Defective Coloring tractable? Finally, in this paper we have not considered
the question of approximation algorithms. Though in general Defective Coloring is likely to be quite hard to approximate (as a consequence of the hardness
of Graph Coloring), it seems promising to also investigate this question in
classes where Graph Coloring is in P.

References
1. Nirmala Achuthan, N. R. Achuthan, and M. Simanihuruk. On minimal trianglefree graphs with prescribed k-defective chromatic number. Discrete Mathematics,
311(13):1119–1127, 2011.
2. James A Andrews and Michael S Jacobson. On a generalization of chromatic
number. Congressus Numerantium, 47:33–48, 1985.
3. Júlio Araújo, Jean-Claude Bermond, Frédéric Giroire, Frédéric Havet, Dorian
Mazauric, and Remigiusz Modrzejewski. Weighted improper colouring. J. Discrete Algorithms, 16:53–66, 2012.
4. Dan Archdeacon. A note on defective colorings of graphs in surfaces. Journal of
Graph Theory, 11(4):517–519, 1987.
5. Claudia Archetti, Nicola Bianchessi, Alain Hertz, Adrien Colombet, and François
Gagnon. Directed weighted improper coloring for cellular channel allocation. Discrete Applied Mathematics, 182:46–60, 2015.
6. Jørgen Bang-Jensen and Magnús M. Halldórsson. Vertex coloring edge-weighted
digraphs. Inf. Process. Lett., 115(10):791–796, 2015.
7. Jean-Claude Bermond, Frédéric Havet, Florian Huc, and Cláudia Linhares Sales.
Improper coloring of weighted grid and hexagonal graphs. Discrete Math., Alg.
and Appl., 2(3):395–412, 2010.
8. Hans L. Bodlaender. A partial k -arboretum of graphs with bounded treewidth.
Theor. Comput. Sci., 209(1-2):1–45, 1998.
9. Hans L. Bodlaender and Arie M. C. A. Koster. Combinatorial optimization on
graphs of bounded treewidth. Comput. J., 51(3):255–269, 2008.
10. Oleg V. Borodin, Alexandr V. Kostochka, and Matthew Yancey. On 1-improper
2-coloring of sparse graphs. Discrete Mathematics, 313(22):2638–2649, 2013.
11. Andreas Brandstädt, Van Bang Le, and Jeremy P Spinrad. Graph classes: a survey.
SIAM, 1999.
12. I. Choi and L. Esperet. Improper coloring of graphs on surfaces. ArXiv e-prints,
March 2016.
13. L. J. Cowen, R. H. Cowen, and D. R. Woodall. Defective colorings of graphs in
surfaces: Partitions into subgraphs of bounded valency. Journal of Graph Theory,
10(2):187–195, 1986.
14. Lenore Cowen, Wayne Goddard, and C. Esther Jesurum. Defective coloring revisited. Journal of Graph Theory, 24(3):205–219, 1997.
15. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx,
Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms.
Springer, 2015.
16. Reinhard Diestel. Graph Theory, 4th Edition, volume 173 of Graduate texts in
mathematics. Springer, 2012.
17. Marietjie Frick. A survey of (m, k)-colorings. Annals of Discrete Mathematics,
55:45–57, 1993.

18. Marietjie Frick and Michael A. Henning. Extremal results on defective colorings
of graphs. Discrete Mathematics, 126(1-3):151–158, 1994.
19. Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide
to the Theory of NP-Completeness. W. H. Freeman & Co., New York, NY, USA,
1979.
20. Wayne Goddard and Honghai Xu. Fractional, circular, and defective coloring of
series-parallel graphs. Journal of Graph Theory, 81(2):146–153, 2016.
21. Martin Charles Golumbic. Trivially perfect graphs. Discrete Mathematics,
24(1):105–107, 1978.
22. Martin Grötschel, László Lovász, and Alexander Schrijver. Geometric algorithms
and combinatorial optimization. Springer4060 XII, 362 S (Berlin [ua]), 1988.
23. Bjarki Agust Gudmundsson, Tómas Ken Magnússon, and Björn Orri Sæmundsson.
Bounds and fixed-parameter algorithms for weighted improper coloring. Electr.
Notes Theor. Comput. Sci., 322:181–195, 2016.
24. Frédéric Havet, Ross J. Kang, and Jean-Sébastien Sereni. Improper coloring of
unit disk graphs. Networks, 54(3):150–164, 2009.
25. Frédéric Havet and Jean-Sébastien Sereni. Improper choosability of graphs and
maximum average degree. Journal of Graph Theory, 52(3):181–199, 2006.
26. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have
strongly exponential complexity? J. Comput. Syst. Sci., 63(4):512–530, 2001.
27. Ross J. Kang. Improper colourings of graphs. PhD thesis, University of Oxford,
UK, 2008.
28. Ross J. Kang and Colin McDiarmid. The t-improper chromatic number of random
graphs. Combinatorics, Probability & Computing, 19(1):87–98, 2010.
29. Ross J. Kang, Tobias Müller, and Jean-Sébastien Sereni. Improper colouring of
(random) unit disk graphs. Discrete Mathematics, 308(8):1438–1454, 2008.
30. Jaehoon Kim, Alexandr V. Kostochka, and Xuding Zhu. Improper coloring of
sparse graphs with a given girth, I: (0, 1)-colorings of triangle-free graphs. Eur. J.
Comb., 42:26–48, 2014.
31. Jaehoon Kim, Alexandr V. Kostochka, and Xuding Zhu. Improper coloring of
sparse graphs with a given girth, II: constructions. Journal of Graph Theory,
81(4):403–413, 2016.
32. Neil Robertson and Paul D. Seymour. Graph minors. II. algorithmic aspects of
tree-width. J. Algorithms, 7(3):309–322, 1986.
33. Dieter Seinsche. On a property of the class of n-colorable graphs. Journal of
Combinatorial Theory, Series B, 16(2):191–193, 1974.
34. Jing-Ho Yan, Jer-Jeong Chen, and Gerard J. Chang. Quasi-threshold graphs.
Discrete Applied Mathematics, 69(3):247–255, 1996.

