An algebraic approach for counting DP-3-colorings of sparse graphs

DP-coloring (or correspondence coloring) is a generalization of list coloring that has been widely studied since its introduction by Dvorak and Postle in 2015. As the analogue of the chromatic polynomial of a graph G, P(G, m), and the list color function, Pl(G, m), the DP-color function of G, denoted by P-DP(G, m), counts the minimum number of DP-colorings over all possible m-fold covers. It follows that P-DP(G, m) <= P-l(G, m) <= P(G, m). A function f is chromatic-adherent if for every graph G, f(G, a) = P(G, a) for some a >= chi(G) implies that f(G, m) = P(G, m) for all m >= a. It is known that the DP-color function is not chromatic adherent, but there are only two known graphs that demonstrate this. Suppose G is an n-vertex graph and H is a 3-fold cover of G. In this paper we associate with H a polynomial f(G,H) is an element of F-3[x(1), ... , x(n)] so that the number of non-zeros of f(G,H) equals the number of H-colorings of G. We then use a well-known result of Alon and Furedi on the number of non-zeros of a polynomial to establish a non-trivial lower bound on P-DP(G, 3) when 2n > |E(G)|. An easy consequence of this is that P-DP(G, 3) >= 3(n/6) for every n-vertex planar graph G of girth at least 5, improving the previously known bounds on both P-DP(G, 3) and P-l(G, 3). Finally, we use this bound to show that there are infinitely many graphs that demonstrate the non-chromatic-adherence of the DP-color function.(c) 2023 Elsevier Ltd. All rights reserved.

Automated summary

DP-coloring is a generalization of list coloring that calculates the minimum number of DP-colorings in a graph's cover. This paper presents a new approach to compute the DP-coloring number and provides improved bounds compared to existing methods. It also proves that the DP-color function is not chromatic adherent.