ALCOMFT-TR-03-63

Josep Diaz, Maria Serna and Dimitrios M. Thilikos
Counting List H-Colorings and Variants
Barcelona. Work packages 2 and 4. October 2003.

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 the topology of H as #P-complete or polynomial time solvable [DG00]. We first prove that the same dichotomy criterion holds also for 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-03-63.ps.gz (181 kb).