Counting list h-colorings and variants
Josep Dı́az, Marı́a Serna, Dimitrios Thilikos Touloupas · 2001
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. 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.