Abstrakt
We give a new method of generating strongly polynomial sequences of graphs, i.e., sequences (H-k) indexed by a tuple k = (k(1),..., k(h)) of positive integers, with the property that, for each fixed graph G, there is a multivariate polynomial p(G; x(1),..., x(h)) such that the number of homomorphisms from G to Hk is given by the evaluation p(G; k(1),..., k(h)). A classical example is the sequence of complete graphs (K-k), for which p(G; x) is the chromatic polynomial of G.
Our construction is based on tree model representations of graphs. It produces a large family of graph polynomials which includes the Tutte polynomial, the Averbouch Godlin Makowsky polynomial, and the Tittmann Averbouch Makowsky polynomial.
We also introduce a new graph parameter, the branching core size of a simple graph, derived from its representation under a particular tree model, and related to how many involutive automorphisms it has. We prove that a countable family of graphs of bounded branching core size is always contained in the union of a finite number of strongly polynomial sequences.