It seems that there's a general way to go from "recursive" definition of a graph polynomials to "subset expansion" formulas.
Furthermore, polynomials with subset expansion formulas often have a representation as a sum over all possible vertex labelings of some "local interactions" model.
For instance, generating function for Eulerian subgraphs becomes Ising model partition function, generating function of independent sets becomes partition function of the hard-core model and Potts model has both "sum over labelings" and "sum over subgraphs" representation.
Are there other interesting examples of graph polynomials with "sum over labelings" representation?
When is it possible to get this representation of a graph polynomial? More specifically, to represent it as a sum over labelings of some quantity that is a product of functions each depending only on the variables corresponding to some edge of the graph. IE, if a graph has edges (1,2),(2,3) the term being summed over has to factor into f(x1,x2)*g(x2,x3)
Motivation: there's a general algorithm to efficiently compute "sum over labelings" for functions decomposing over graph or hyper-graph of bounded tree-width, and it's interesting to see which graph polynomials I can use it for
