ALCOMFT-TR-02-101

Josep D\'\iaz, Maria Serna and Dimitrios Thilikos
The complexity of restrictive H-coloring
Barcelona. Work packages 2 and 4. May 2002.

Abstract: We define a variant of the H-coloring problem where the number of preimages of certain vertices is predetermined as part of the problem input. We consider the decision and the counting version of the problem, namely the restrictive H-coloring and the restrictive \#H-coloring problems, and we provide a dichotomy theorem determining the H's for which the restrictive H-coloring problem is either NP-complete or polynomially solvable. Moreover, we prove that the same criterion discriminates the \SP-complete and the polynomially solvable cases of the restrictive \#H-coloring problem. Finally, we prove that both our results apply also for the list versions of the above problems.

Postscript file: ALCOMFT-TR-02-101.ps.gz (109 kb).