On Polynomial Representations of Dual DP Color Functions

DP-coloring (also called correspondence coloring) is a generalization of list coloring that was introduced by Dvořák and Postle in 2015. The chromatic polynomial of a graph is an important notion in algebraic combinatorics that was introduced by Birkhoff in 1912; denoted $P(G,m)$, it equals the number of proper $m$-colorings of graph $G$. Counting function analogues of chromatic polynomials have been introduced for list colorings: $P_{\mathrm{\ell }}$, list color functions (1990); DP colorings: $P_{DP}$, DP color functions (2019), and $P_{DP}^{\ast }$, dual DP color functions (2021). For any graph $G$ and $m\in \mathbb{N}$, $P_{DP}(G,m)\le P_{\mathrm{\ell }}(G,m)\le P(G,m)\le P_{DP}^{\ast }(G,m)$. In 2022 (improving on older results) Dong and Zhang showed that for any graph $G$, $P_{\mathrm{\ell }}(G,m)=P(G,m)$ whenever $m\ge \mathrm{\mid }E(G)\mathrm{\mid }-1$. Consequently, the list color function of a graph is a polynomial for sufficiently large $m$. One of the most important and longstanding open questions on DP color functions asks: for every graph $G$ is there an $N\in \mathbb{N}$ and a polynomial $p(m)$ such that $P_{DP}(G,m)=p(m)$ whenever $m\ge N$? We show that the answer to the analogue of this question for dual DP color functions is no. Our proof reveals a connection between a dual DP color function and the balanced chromatic polynomial of a signed graph introduced by Zaslavsky in 1982.