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