Publication at Faculty of Mathematics and Physics |
2013
Abstract
We give a method of generating strongly polynomial sequences of graphs. A classical example is the sequence of complete graphs, for which hom(G,K_k)=P(G;k) is the evaluation of the chromatic polynomial at k.
Our construction produces a large family of graph polynomials that 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, related to how many involutive automorphisms with fixed points it has.
We prove that a countable family of graphs of bounded branching core size (which in particular implies bounded tree-depth) is always contained in a finite union of strongly polynomial sequences.