Dichotomy Theorems for Homomorphism Polynomials of Graph Classes

Authors

  • Christian Engels

DOI:

https://doi.org/10.7155/jgaa.00382

Keywords:

graph homomorphism , arithmetic complexity , dichotomies , vnp

Abstract

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 (for different definitions of geni).

Downloads

Download data is not yet available.

Downloads

Published

2016-02-01

How to Cite

Engels, C. (2016). Dichotomy Theorems for Homomorphism Polynomials of Graph Classes. Journal of Graph Algorithms and Applications, 20(1), 3–22. https://doi.org/10.7155/jgaa.00382