ALCOMFT-TR-01-135

J. D\'\iaz, M. Serna and D.M. Thilik\'os
Counting List H-Colorings and Variants
Barcelona. Work package 4. June 2001.

Abstract: We study the counting versions of several variants of the H-coloring problem. The complexity of the #H-coloring problem is described by a dichotomy theorem that classifies the problem according to the topology of H as #P-complete or polynomial time solvable. We first prove that the same dichotomy criterion holds also its ``list'' extension, the list #H-coloring problem. We further investigate these problems by examining a parameterization imposing restrictions on the number of preimages of certain vertices in H. We prove a nearly dichotomy theorem on the complexity of counting such restricted homomorphisms, as well as a dichotomy theorem on the complexity of its list version. Finally, we give a condition that makes the parameterizedd problems solvable in linear time.

Postscript file: ALCOMFT-TR-01-135.ps.gz (118 kb).