Contractors and connectors of graph algebras

We study generalizations of the "contraction-deletion" relation of the Tutte polynomial, and other similar simple operations, to other graph parameters. The question can be set in the framework of graph algebras introduced by Freedman, Lovasz and Schrijver, and it relates to their behavior under basic graph operations like contraction and subdivision. Graph algebras were introduced to study and characterize homomorphism functions. We prove that for homomorphism functions, these graph algebras have special elements called ``contractors'' and ``connectors''. This gives a new characterization of homomorphism functions.

Abstract licence: CC0

A person counts once a day per paper. We keep no cookie and no address: a reader is a hash that changes every day. Any month under five reads shows no number.