Harary polynomials

Abstract

Given a graph property $\mathcal{P}$, F. Harary introduced in 1985 $\mathcal{P}$-colorings, graph colorings where each colorclass induces a graph in $\mathcal{P}$. Let ${\chi }_{\mathcal{P}}(G;k)$ counts the number of $\mathcal{P}$-colorings of $G$ with at most $k$ colors. It turns out that ${\chi }_{\mathcal{P}}(G;k)$ is a polynomial in $\mathbb{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 $\chi (G;k)$. We show that the characteristic and Laplacian polynomial, the matching, the independence and the domination polynomial are not Harary polynomials. We show that for various notions of sparse, non-trivial properties $\mathcal{P}$, the polynomial ${\chi }_{\mathcal{P}}(G;k)$ is, in contrast to $\chi (G;k)$, not a chromatic, and even not an edge elimination invariant. Finally we study whether Harary polynomials are definable in Monadic Second Order Logic.

17 pages