Home Issues About JGAA Instructions for Authors
 
 
Special Issue on Selected Papers from the Ninth International Workshop on Algorithms and Computation (WALCOM 2015)
DOI: 10.7155/jgaa.00382
Dichotomy Theorems for Homomorphism Polynomials of Graph Classes
Vol. 20, no. 1, pp. 3-22, 2016. Regular paper.
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).
Submitted: March 2015.
Reviewed: August 2015.
Revised: November 2015.
Accepted: November 2015.
Final: January 2016.
Published: February 2016.
Communicated by M. Sohel Rahman and Etsuj Tomita
article (PDF)
BibTeX