Homomorphisms and polynomial invariants of graphs

This paper initiates a general study of the connection between graph homomorphisms and the Tutte polynomial. This connection can be extended to other polynomial invariants of graphs related to the Tutte polynomial such as the transition, the circuit partition, the boundary, and the coboundary polynomials. As an application, we describe in terms of homomorphism Counting some fundamental evaluations of the Tutte polynomial in abelian groups and statistical physics. We conclude the paper by providing a homomorphism view of the uniqueness conjectures formulated by Bollobas, Pebody and Riordan. (C) 2009 Elsevier Ltd. All rights reserved.