Article
Polynomial graph invariants from homomorphism numbers
Author/s | Garijo Royo, Delia
![]() ![]() ![]() ![]() ![]() ![]() ![]() Goodall, Andrew Nesetril, Jaroslav |
Department | Universidad de Sevilla. Departamento de Matemática Aplicada I (ETSII) |
Publication Date | 2016 |
Deposit Date | 2020-06-20 |
Published in |
|
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 ... 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. |
Funding agencies | Ministerio de Economía y Competitividad (MINECO). España |
Project ID. | MTM2014-60127-P
![]() |
Citation | Garijo Royo, D., Goodall, A. y Nesetril, J. (2016). Polynomial graph invariants from homomorphism numbers. Discrete mathemtaics, 339 (4), 1315-1328. |
Files | Size | Format | View | Description |
---|---|---|---|---|
Polynomial graph invariants.pdf | 498.7Kb | ![]() | View/ | |