Article in press
Authors:
Title:
On polynomial representations of dual DP color functions
PDFSource:
Discussiones Mathematicae Graph Theory
Received: 2025-01-21 , Revised: 2025-05-24 , Accepted: 2025-06-01 , Available online: 2025-07-07 , https://doi.org/10.7151/dmgt.2593
Abstract:
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_{\ell}$, list color
functions (1990); DP colorings: $P_{DP}$, DP color functions (2019), and
$P^*_{DP}$, dual DP color functions (2021). For any graph $G$ and $m \in \mathbb{N}$,
$P_{DP}(G, m) \leq P_\ell(G,m) \leq P(G,m) \leq P_{DP}^*(G,m)$. In 2022
(improving on older results) Dong and Zhang showed that for any graph $G$,
$P_{\ell}(G,m)=P(G,m)$ whenever $m \geq |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 \in \mathbb{N}$ and a polynomial $p(m)$ such that
$P_{DP}(G,m) = p(m)$ whenever $m \geq 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.
Keywords:
correspondence coloring, DP coloring, DP color function, dual DP color function
References:
- J. Becker, J. Hewitt, H. Kaul, M. Maxfield, J.A. Mudrock, D. Spivey, S. Thomason and T. Wagstrom, The DP color function of joins and vertex-gluings of graphs, Discrete Math. 345 (2022) 113093.
https://doi.org/10.1016/j.disc.2022.113093 - A. Bernshteyn, The asymptotic behavior of the correspondence chromatic number, Discrete Math. 339 (2016) 2680–2692.
https://doi.org/10.1016/j.disc.2016.05.012 - A. Bernshteyn and A.V. Kostochka, Sharp Dirac's theorem for DP-critical graphs, J. Graph Theory 88 (2018) 521–546.
https://doi.org/10.1002/jgt.22227 - A. Bernshteyn and A.V. Kostochka, On differences between DP-coloring and list coloring, Siberian Adv. Math. 21 (2018) 61–71.
https://doi.org/10.3103/S1055134419030039 - A. Bernshteyn, A.V. Kostochka and X. Zhu, DP-colorings of graphs with high chromatic number, European J. Combin. 65 (2017) 122–129.
https://doi.org/10.1016/j.ejc.2017.05.007 - G.D. Birkhoff, A determinant formula for the number of ways of coloring a map, Ann. Math. 14 (1912–1913) 42–46.
https://doi.org/10.2307/1967597 - Z.Y. Cheng, Z. Lei, Y.T. Wang and Y.C. Zhang, A categorification for the signed chromatic polynomial, Electron. J. Combin. 29 (2022) #P2.49.
https://doi.org/10.37236/10939 - S.L. Dahlberg, H. Kaul and J.A. Mudrock, An algebraic approach for counting DP-$3$-colorings of sparse graphs, European J. Combin. 118 (2024) 103890.
https://doi.org/10.1016/j.ejc.2023.103890 - S.L. Dahlberg, H. Kaul and J.A. Mudrock, A polynomial method for counting colorings of sparse graphs (2023).
arXiv: 2312.11744 - F.M. Dong and Y. Yang, DP color functions versus chromatic polynomials, Adv. Appl. Math. 134 (2022) 102301.
https://doi.org/10.1016/j.aam.2021.102301 - F.M. Dong and M.Q. Zhang, An improved lower bound of $P(G,L)-P(G,k)$ for $k$-assignments $L$, J. Combin. Theory Ser. B 161 (2023) 109–119.
https://doi.org/10.1016/j.jctb.2023.02.002 - Q. Donner, On the number of list-colorings, J. Graph Theory 16 (1992) 239–245.
https://doi.org/10.1002/jgt.3190160307 - Z. Dvořák and L. Postle, Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths $4$ to $8$, J. Combin. Theory Ser. B 129 (2018) 38–54.
https://doi.org/10.1016/j.jctb.2017.09.001 - P. Erdős, A.L. Rubin and H. Taylor, Choosability in graphs, Congr. Numer. 26 (1979) 125–127.
- C. Halberg, H. Kaul, A. Liu, J.A. Mudrock, P. Shin and S. Thomason, On polynomial representations of the DP color function: Theta graphs and their generalizations, J. Combin. 15 (2024) 451–478.
https://doi.org/10.4310/joc.240906222651 - H. Kaul and J.A. Mudrock, Combinatorial Nullstellensatz and DP-coloring of graphs, Discrete Math. 343 (2020) 112115.
https://doi.org/10.1016/j.disc.2020.112115 - H. Kaul and J.A. Mudrock, On the chromatic polynomial and counting DP-colorings of graphs, Adv. Appl. Math. 123 (2021) 102131.
https://doi.org/10.1016/j.aam.2020.102131 - H. Kaul, J.A. Mudrock, G. Sharma and Q. Stratton, DP-coloring Cartesian products of graphs, J. Graph Theory 103 (2023) 285–306.
https://doi.org/10.1002/jgt.22917 - S.-J. Kim and K. Ozeki, A note on a Brooks' type theorem for DP-coloring, J. Graph Theory 91 (2019) 148–161.
https://doi.org/10.1002/jgt.22425 - A.V. Kostochka and A.F. Sidorenko, Problem session, in: Fourth Czechoslovak Symposium on Combinatorics, Graphs and Complexity, J. Nešetřil and M. Fiedler (Ed(s)), Ann. Discrete Math. 51, (Elsevier Science Publishers B.V., 1992) 380.
- Z. Li and Y. Yang, Bounds for DP color function and canonical labelings, Graphs Combin. 40 (2024) 65.
https://doi.org/10.1007/s00373-024-02794-5 - R. Liu, S. Loeb, Y. Yin and G. Yu, DP-$3$-coloring of some planar graphs, Discrete Math. 342 (2019) 178–189.
https://doi.org/10.1016/j.disc.2018.09.025 - J.A. Mudrock, A deletion-contraction relation for the DP color function, Graphs Combin. 38 (2022) 115.
https://doi.org/10.1007/s00373-022-02520-z - J.A. Mudrock and S. Thomason, Answers to two questions on the DP color function, Electron. J. Combin. 28 (2021) #P2.24.
https://doi.org/10.37236/9863 - J.A. Mudrock, A note on the DP-chromatic number of complete bipartite graphs, Discrete Math. 341 (2018) 3148–3151.
https://doi.org/10.1016/j.disc.2018.08.003 - L. Postle and E. Smith-Roberge, Exponentially many correspondence colourings of planar and locally planar graphs (2023).
arXiv: 2309.17291 - C. Thomassen, The chromatic polynomial and list colorings, J. Combin. Theory Ser. B 99 (2009) 474–479.
https://doi.org/10.1016/j.jctb.2008.09.005 - G. Sharbel, Counting DP colorings, GitHub repository (2024).
https://github.com/GSharb/Counting_DP_Colorings - V.G. Vizing, Coloring the vertices of a graph in prescribed colors, Diskret. Analiz. 29 (1976) 3–10.
- W. Wang, J. Qian and Z. Yan, When does the list-coloring function of a graph equal its chromatic polynomial, J. Combin. Theory Ser. B 122 (2017) 543–549.
https://doi.org/10.1016/j.jctb.2016.08.002 - D.B. West, Introduction to Graph Theory (Prentice Hall, Upper Saddle River, NJ, 2001).
- T. Zaslavsky, Signed graph coloring, Discrete Math. 39 (1982) 215–228.
https://doi.org/10.1016/0012-365X(82)90144-3
Close