Polynomials and graph homomorphisms

Abstract

We develop in the language of graph homomorphisms the connection between the Tutte polynomial and the state models of statistical physics. The Tutte polynomial and homomorphism numbers. Spin models and edge coloring models. Connection matrices and the characterization of graph invariants arising from spin models. Homomorphism numbers and invariants of the cycle matroid of a graph. Graph homomorphism numbers as evaluations of graph polynomials. Other graph polynomials from counting graph homomorphisms such as the independence polynomial, the Averbouch–Godlin–Makowsky polynomial, and the Tittmann–Averbouch–Makowsky polynomial.

Topics & Concepts