The Complexity of Counting Graph Homomorphisms

The problem of counting graph homomorphisms is considered. We show that the counting problem corresponding to a given graph is #P-complete unless every connected component of the graph is an isolated vertex without a loop, a complete graph with all loops present, or a complete unlooped bipartite graph. 1 Introduction Many combinatorial counting problems on graphs can be restated as the problem of counting the number of homomorphisms to a particular graph H. The vertices of H correspond to colours, and the edges show which colours may be adjacent. The graph H may contain loops. Specifically, let C be a set of k colours, where k is a constant. Let H = (C; EH ) be a graph with vertex set C. Given a graph G = (V; E) with vertex set V , a map X : V 7! C is called a H-colouring if fX(v); X(w)g 2 EH for all fv; wg 2 E: In other words, X is a homomorphism from G to H. Let\Omega H (G) denote the set of all H-colourings of G. Two well-known combinatorial counting problems which can be c..