Polynomial graph invariants from homomorphism numbers

2013/08/19 by Garijo, Delia, Goodall, Andrew, Nesetril, Jaroslav
#05C31 #05C60 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1308.3999

Abstract

We give a method of generating strongly polynomial sequences of graphs, i.e., sequences (H_k) indexed by a multivariate parameter k=(k₁,…, k_h) such that, for each fixed graph G, there is a multivariate polynomial p(G;x₁,…, x_h) such that the number of homomorphisms from G to H_k is given by the evaluation p(G;k₁,…, k_h). A classical example is the sequence (K_k) of complete graphs, for which \rm 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 \em 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.

Related

• On sequences of polynomials arising from graph invariants
• Dichotomy Theorems for Homomorphism Polynomials of Graph Classes
• Graph Homomorphism Polynomials: Algorithms and Complexity
• On the number of Hamiltonian cycles and polynomial invariants of graphs
• From the Ising and Potts models to the general graph homomorphism polynomial