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{r}\'{a}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_, list color functions (1990); DP colorings: PDP, DP color functions (2019), and P^*DP, dual DP color functions (2021). For any graph G and m ∈ N, PDP(G, m) ≤ P₍G,m) ≤ P(G,m) ≤ PDP^*(G,m). In 2022 (improving on older results) Dong and Zhang showed that for any graph G, P_(G,m)=P(G,m) whenever m ≥ |E(G)|-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 ∈ N and a polynomial $p(m)$ such that PDP(G,m) = p(m) whenever m ≥ 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.