Harary polynomials
Orli Herscovici, Johann A. Makowsky, Vsevolod Rakita · Enumerative Combinatorics and Applications · 2021
Given a graph property P, F. Harary introduced in 1985 P-colorings, graph colorings where each color class induces a graph in P. Let χ P (G; k) counts the number of P-colorings of G with at most k colors.It turns out that χ P (G; k) is a polynomial in Z[k] for each graph G. Graph polynomials of this form are called Harary polynomials.In this paper we investigate properties of Harary polynomials and compare them with properties of the classical chromatic polynomial χ(G; k).We show that the characteristic and the Laplacian polynomial, the matching, the independence and the domination polynomials are not Harary polynomials.We show that for various notions of sparse, non-trivial properties P, the polynomial χ P (G; k) is, in contrast to χ(G; k), not a chromatic, and even not an edge elimination invariant.Finally, we study whether the Harary polynomials are definable in monadic second-order Logic.