In this paper, we will show dichotomy theorems for the computation of polynomials corresponding to evaluation of graph homomorphisms in Valiant’s model. We are given a fixed graph
and want to find all graphs, from some graph class, homomorphic to this
. These graphs will be encoded by a family of polynomials.
We give dichotomies for the polynomials for cycles, cliques, trees, outerplanar graphs, planar graphs and graphs of bounded genus.