Dichotomy theorems for homomorphism polynomials of graph classes

DOI10.7155/JGAA.00382MaRDI QIDQ2790150zbMATH OpenOpenAlexFDO

Authors Christian Engels

Publication date 3 March 2016

Published in Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.7155/jgaa.00382

zbMATH Keywords

graph homomorphisms in Valiant's model

Mathematics Subject Classification ID

Graph polynomials (05C31) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Recommendations

• Dichotomy Theorems for Homomorphism Polynomials of Graph Classes
• A dichotomy theorem for homomorphism polynomials
• Graph homomorphisms with complex values: a dichotomy theorem (extended abstract)
• Graph homomorphisms with complex values: a dichotomy theorem
• On Counting Homomorphisms to Directed Acyclic Graphs

Cited in

(12)

• On the impossibility of a generalization of the HOMFLY-polynomial to labelled oriented graphs
• Variants of the determinant polynomial and the \textsf{VP}-completeness
• A dichotomy theorem for homomorphism polynomials
• The complexity of the cover polynomials for planar graphs of bounded degree
• A Dichotomy Theorem for Polynomial Evaluation
• scientific article; zbMATH DE number 4047782 (Why is no real title available?)
• scientific article; zbMATH DE number 7312755 (Why is no real title available?)
• Graph pattern polynomials
• Dichotomy Theorems for Homomorphism Polynomials of Graph Classes
• Monotone arithmetic complexity of graph homomorphism polynomials
• Variants of the determinant polynomial and VP-completeness
• Homomorphisms, representations and characteristic polynomials of digraphs

This page was built for publication: Dichotomy theorems for homomorphism polynomials of graph classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2790150)