Distinctive power and comparability of Harary polynomial

Abstract

Let $\mathcal{P}$ be a graph property. A $\mathcal{P}$-coloring with at most $k$ colors is a coloring of the vertices of a simple graph $G$ such that each color class induces a graph in $\mathcal{P}$. Harary polynomials are generalizations of the chromatic polynomial for simple graphs based on conditional colorings. We denote by ${\chi }_{\mathcal{P}}(G;k)$ the number of $\mathcal{P}$-colorings of $G$ with at most $k$ colors. ${\chi }_{\mathcal{P}}(G;k)$ is a polynomial in $\mathbb{Z}[k]$. A first paper studying Harary polynomials systematically was published in 2021 by O.Herscovici, J.A. Makowsky and V. Rakita. It studies under which conditions on $\mathcal{P}$ is ${\chi }_{\mathcal{P}}(G;k)$ definable in Monadic Second Order Logic and under which conditions is ${\chi }_{\mathcal{P}}(G;k)$ a chromatic invariant. Let $\mathcal{P},\mathcal{Q}$ be two graph properties. Two graphs $G,H$ are $\mathcal{P}$-mates if ${\chi }_{\mathcal{P}}(G;k)={\chi }_{\mathcal{P}}(H;k)$. ${\chi }_{\mathcal{Q}}$ is at least as distinctive as ${\chi }_{\mathcal{P}}$, ${\chi }_{\mathcal{P}}\le {\chi }_{\mathcal{Q}}$, if for all graphs $G,H$ we have that ${\chi }_{\mathcal{Q}}(G;k)={\chi }_{\mathcal{Q}}(H;k)$ implies ${\chi }_{\mathcal{P}}(G;k)={\chi }_{\mathcal{P}}(H;k)$. In this paper we study under which conditions on $\mathcal{P}$ are there any (many) $\mathcal{P}$-mates and under which conditions on $\mathcal{P},\mathcal{Q}$ is ${\chi }_{\mathcal{Q}}$ is at least as distinctive as ${\chi }_{\mathcal{P}}$.

23 pages