Geodesic
Dichotomy Theorems for Homomorphism Polynomials of Graph Classes
Journal of Graph Algorithms and Applications, Special Issue on Selected Papers from the Ninth International Workshop on Algorithms and Computation (WALCOM 2015) , Tome 20 (2016) no. 1, pp. 3-22.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

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).
DOI : 10.7155/jgaa.00382
Keywords: graph homomorphism, arithmetic complexity, dichotomies, vnp 
@article{JGAA_2016_20_1_a1,
     author = {Christian Engels},
     title = {Dichotomy {Theorems} for {Homomorphism} {Polynomials} of {Graph} {Classes}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {3--22},
     publisher = {mathdoc},
     volume = {20},
     number = {1},
     year = {2016},
     doi = {10.7155/jgaa.00382},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00382/}
}
TY  - JOUR
AU  - Christian Engels
TI  - Dichotomy Theorems for Homomorphism Polynomials of Graph Classes
JO  - Journal of Graph Algorithms and Applications
PY  - 2016
SP  - 3
EP  - 22
VL  - 20
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00382/
DO  - 10.7155/jgaa.00382
LA  - en
ID  - JGAA_2016_20_1_a1
ER  - 
%0 Journal Article
%A Christian Engels
%T Dichotomy Theorems for Homomorphism Polynomials of Graph Classes
%J Journal of Graph Algorithms and Applications
%D 2016
%P 3-22
%V 20
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00382/
%R 10.7155/jgaa.00382
%G en
%F JGAA_2016_20_1_a1
Christian Engels. Dichotomy Theorems for Homomorphism Polynomials of Graph Classes. Journal of Graph Algorithms and Applications, 
							Special Issue on Selected Papers from the Ninth International Workshop on Algorithms and Computation  (WALCOM 2015)
					, Tome 20 (2016) no. 1, pp. 3-22. doi : 10.7155/jgaa.00382. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00382/

Cité par Sources :