2005/05/10 by Laszlo Lovasz, Lovasz, Laszlo, Balazs Szegedy +1 · 1 citation
Mathematics · #05C99 #16S99 #Combinatorics (math.CO) #FOS: Mathematics #Rings and Algebras (math.RA) #math.CO #math.RA #msc:05C99 #msc:16S99
paper · pdf · doi:10.48550/arxiv.math/0505162
21 pages
arxiv created 2005/05/10 · arxiv updated 2009/12/01
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.