Dichotomy Theorems for Homomorphism Polynomials of Graph Classes

DOI10.1007/978-3-319-15612-5_25MaRDI QIDQ5176591zbMATH OpenOpenAlexFDO

Authors Christian Engels

Publication date 27 February 2015

Published in WALCOM: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1412.0423

zbMATH Keywords

dichotomy theoremsgraph homomorphismsValiant's model

Mathematics Subject Classification ID

Graph polynomials (05C31)

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.

Recommendations

• Dichotomy theorems for homomorphism polynomials of graph classes
• scientific article; zbMATH DE number 4047782
• A dichotomy theorem for homomorphism polynomials
• Homomorphisms and Polynomial Invariants of Graphs
• Homomorphisms and polynomial invariants of graphs
• The Homomorphism Structure of Classes of Graphs
• CATEGORIFICATION OF THE DICHROMATIC POLYNOMIAL FOR GRAPHS
• Polynomials and graph homomorphisms
• The Tutte polynomial for homeomorphism classes of graphs
• Graph homomorphisms with complex values: a dichotomy theorem

Cited in

(8)

• On the impossibility of a generalization of the HOMFLY-polynomial to labelled oriented graphs
• Dichotomy theorems for homomorphism polynomials of graph classes
• 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?)
• 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 Q5176591)