Polynomial graph invariants from homomorphism numbers

We give a new method of generating strongly polynomial sequences of graphs, i.e., sequences (Hk) indexed by a tuple k=(k1,…,kh) of positive integers, with the property that, for each fixed graph GG, there is a multivariate polynomial p(G;x1,…,xh)p(G;x1,…,xh) such that the number of homomorphisms from GG to Hk is given by the evaluation p(G;k1,…,kh)p(G;k1,…,kh). A classical example is the sequence of complete graphs (Kk)(Kk), for which p(G;x)p(G;x) is the chromatic polynomial of GG. 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.