Garijo Royo, DeliaGoodall, AndrewNesetril, Jaroslav2020-06-202020-06-202016Garijo Royo, D., Goodall, A. y Nesetril, J. (2016). Polynomial graph invariants from homomorphism numbers. Discrete mathemtaics, 339 (4), 1315-1328.0012-365Xhttps://hdl.handle.net/11441/98072We 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 G, there is a multivariate polynomial p(G; x1, . . . , xh) such that the number of homomorphisms from G to Hk 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.application/pdf14engAttribution-NonCommercial-NoDerivatives 4.0 Internacionalhttp://creativecommons.org/licenses/by-nc-nd/4.0/Graph polynomialGraph homomorphismGraph sequenceinfo:eu-repo/semantics/articleinfo:eu-repo/semantics/openAccesshttps://doi.org/10.1016/j.disc.2015.11.022