2015 | OriginalPaper | Buchkapitel
Dichotomy Theorems for Homomorphism Polynomials of Graph Classes
Erschienen in:
WALCOM: Algorithms and Computation
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
H
and want to find all graphs, from some graph class, homomorphic to this
H
. 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.
