We give a new method of generating strongly polynomial sequences of graphs, i.e., sequences
class="mathmlsrc">title="View the MathML source" class ="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004318&_mathId=si30.gif&_user=111111111&_pii=S0012365X15004318&_rdoc=1&_issn=0012365X&md5=642ccf987e4557b9af7de152dc695fc6"> class="imgLazyJSB inlineImage" height="15" width="30" alt="View the MathML source" style="margin-top: -5px; vertical-align: middle" title ="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0012365X15004318-si30.gif"> title="View the MathML source" src="http://origin-ars.els-cdn.com/content/image/1-s2.0-S0012365X15004318-si30.gif"> class="mathContainer hidden">class="mathCode">( H k ) indexed by a tuple
class="mathmlsrc">title="View the MathML source" class ="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004318&_mathId=si31.gif&_user=111111111&_pii=S0012365X15004318&_rdoc=1&_issn=0012365X&md5=6458135dc12b7a12a2a4bcdc9e9740a0"> class="imgLazyJSB inlineImage" height="15" width="111" alt="View the MathML source" style="margin-top: -5px; vertical-align: middle" title ="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0012365X15004318-si31.gif"> title="View the MathML source" src="http://origin-ars.els-cdn.com/content/image/1-s2.0-S0012365X15004318-si31.gif"> class="mathContainer hidden">class="mathCode">k = ( k 1 , … , k h ) of positive integers, with the property that, for each fixed graph
class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004318&_mathId=si32.gif&_user=111111111&_pii=S0012365X15004318&_rdoc=1&_issn=0012365X&md5=0bdf93d6515afe71012536e2ca45ed06" title ="Click to view the MathML source">G class="mathContainer hidden">class="mathCode">G , there is a multivariate polynomial
class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004318&_mathId=si33.gif&_user=111111111&_pii=S0012365X15004318&_rdoc=1&_issn=0012365X&md5=6290544a306f025a73c904e36ade38aa" title ="Click to view the MathML source">p(G;x1 ,…,xh ) class="mathContainer hidden">class="mathCode">p ( G ; x 1 , … , x h ) such that the number of homomorphisms from
class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004318&_mathId=si32.gif&_user=111111111&_pii=S0012365X15004318&_rdoc=1&_issn=0012365X&md5=0bdf93d6515afe71012536e2ca45ed06" title ="Click to view the MathML source">G class="mathContainer hidden">class="mathCode">G to
class="mathmlsrc">title="View the MathML source" class ="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004318&_mathId=si35.gif&_user=111111111&_pii=S0012365X15004318&_rdoc=1&_issn=0012365X&md5=c97d4a78221ac749506292d6b4ff598e"> class="imgLazyJSB inlineImage" height="14" width="19" alt="View the MathML source" style="margin-top: -5px; vertical-align: middle" title ="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0012365X15004318-si35.gif"> title="View the MathML source" src="http://origin-ars.els-cdn.com/content/image/1-s2.0-S0012365X15004318-si35.gif"> class="mathContainer hidden">class="mathCode">H k is given by the evaluation
class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004318&_mathId=si36.gif&_user=111111111&_pii=S0012365X15004318&_rdoc=1&_issn=0012365X&md5=bfc2ff576eb0a3004207cfba72696d78" title ="Click to view the MathML source">p(G;k1 ,…,kh ) class="mathContainer hidden">class="mathCode">p ( G ; k 1 , … , k h ) . A
class ical example is the sequence of complete graphs
class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004318&_mathId=si37.gif&_user=111111111&_pii=S0012365X15004318&_rdoc=1&_issn=0012365X&md5=8826bdc5dfac4d7fb6b79e808f8d9c5f" title ="Click to view the MathML source">(Kk ) class="mathContainer hidden">class="mathCode">( K k ) , for which
class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004318&_mathId=si38.gif&_user=111111111&_pii=S0012365X15004318&_rdoc=1&_issn=0012365X&md5=070bede4394a8f58902ee12c0f565062" title ="Click to view the MathML source">p(G;x) class="mathContainer hidden">class="mathCode">p ( G ; x ) is the chromatic polynomial of
class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15004318&_mathId=si32.gif&_user=111111111&_pii=S0012365X15004318&_rdoc=1&_issn=0012365X&md5=0bdf93d6515afe71012536e2ca45ed06" title ="Click to view the MathML source">G class="mathContainer hidden">class="mathCode">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.