2024/07/05 by Mudrock, Jeffrey A., Sharbel, Gabriel
#05C15 #05C30 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2407.04807
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ℓ, 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 ∈ ℕ, 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 ∈ ℕ 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.