dc.creator | Garijo Royo, Delia | es |
dc.creator | Goodall, Andrew | es |
dc.creator | Nesetril, Jaroslav | es |
dc.date.accessioned | 2020-06-20T09:07:19Z | |
dc.date.available | 2020-06-20T09:07:19Z | |
dc.date.issued | 2016 | |
dc.identifier.citation | Garijo Royo, D., Goodall, A. y Nesetril, J. (2016). Polynomial graph invariants from homomorphism numbers. Discrete mathemtaics, 339 (4), 1315-1328. | |
dc.identifier.issn | 0012-365X | es |
dc.identifier.uri | https://hdl.handle.net/11441/98072 | |
dc.description.abstract | 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 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. | es |
dc.description.sponsorship | Ministerio de Economía y Competitividad MTM2014-60127-P | es |
dc.format | application/pdf | es |
dc.format.extent | 14 | es |
dc.language.iso | eng | es |
dc.publisher | Elsevier | es |
dc.relation.ispartof | Discrete mathemtaics, 339 (4), 1315-1328. | |
dc.rights | Attribution-NonCommercial-NoDerivatives 4.0 Internacional | * |
dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/4.0/ | * |
dc.subject | Graph polynomial | es |
dc.subject | Graph homomorphism | es |
dc.subject | Graph sequence | es |
dc.title | Polynomial graph invariants from homomorphism numbers | es |
dc.type | info:eu-repo/semantics/article | es |
dcterms.identifier | https://ror.org/03yxnpp24 | |
dc.type.version | info:eu-repo/semantics/submittedVersion | es |
dc.rights.accessRights | info:eu-repo/semantics/openAccess | es |
dc.contributor.affiliation | Universidad de Sevilla. Departamento de Matemática Aplicada I (ETSII) | es |
dc.relation.projectID | MTM2014-60127-P | es |
dc.relation.publisherversion | https://www.sciencedirect.com/science/article/pii/S0012365X15004318 | es |
dc.identifier.doi | 10.1016/j.disc.2015.11.022 | es |
dc.journaltitle | Discrete mathemtaics | es |
dc.publication.volumen | 339 | es |
dc.publication.issue | 4 | es |
dc.publication.initialPage | 1315 | es |
dc.publication.endPage | 1328 | es |
dc.identifier.sisius | 21148807 | es |
dc.contributor.funder | Ministerio de Economía y Competitividad (MINECO). España | es |