2006 | OriginalPaper | Chapter
Efficient Algorithms for Parameterized H-colorings
Authors: Josep Díaz, Maria Serna, Dimitrios M. Thilikos
Publisher: Springer Berlin Heidelberg
We study the fixed parameter tractability of the restrictive
H
-coloring and the restrictive list
H
-coloring problems, introduced in [DST01]. The parameter-izations are defined by fixing the number of pre-images of a subset
C
of the vertices in
H
through a partial weight assignment (
C, K
). We define two families of partially weighted graphs: the
simple
and the
plain
. For the class of simple partially weighted graphs, we show the fixed parameter tractability of the list (
H, C, K
)-coloring problem. For the more general class of plain partially weighted graphs, we prove the fixed parameter tractability of the (
H, C, K
)-coloring problem.
