On the Complexity of Some Colorful Problems Parameterized by
Information and Computation,
vol. 209, no. 2, pp. 143-153, 2011.
A preliminary version appeared in the
Proceedings of COCOA 2007,
The First International Conference on Combinatorial
Optimization and Applications, August 12-15, 2007, Xi'an, Shaanxi, China.
Lecture Notes in Computer Science, vol. 4616,
pp. 366-377, 2007.
We study the complexity of several coloring problems on graphs,
parameterized by the treewidth of the graph:
- The list chromatic number \chi_l(G) of a graph G is defined to be
the smallest positive integer r, such that for every assignment to
the vertices v of G, of a list L_v of colors, where each list has
length at least r, there is a choice of one color from each vertex
list L_v yielding a proper coloring of G. We show that the problem
of determining whether \chi_l(G)\leq r, the LIST CHROMATIC NUMBER
problem, is solvable in linear time for every fixed treewidth bound
t. The method by which this is shown is new and of general
The LIST COLORING problem takes as input a graph G, together with
an assignment to each vertex v of a set of colors C_v . The problem
is to determine whether it is possible to choose a color for vertex
v from the set of permitted colors C_v , for each vertex, so that
the obtained coloring of G is proper. We show that this problem is
W-hard, parameterized by the treewidth of G. The closely related
PRECOLORING EXTENSION problem is also shown to be W-hard, parameterized by treewidth.
- An equitable coloring of a graph G is a proper coloring of the
vertices where the numbers of vertices having any two distinct
colors differs by at most one. We show that the problem is hard for
W, parameterized by (t,r). We also show that a list-based
variation, LIST EQUITABLE COLORING is W-hard for trees,
parameterized by the number of colors on the lists.
Download: [paper pdf]