Non-chromatic-adherence of the DP Color Function via Generalized Theta Graphs

Abstract

DP-coloring (also called correspondence coloring) is a generalization of list coloring that has been widely studied in recent years after its introduction by Dvořák and Postle in 2015. The chromatic polynomial of a graph is an extensively studied notion in combinatorics since its introduction by Birkhoff in 1912; denoted $P(G,m)$, it equals the number of proper $m$-colorings of graph $G$. Counting function analogues of the chromatic polynomial have been introduced and studied for list colorings: $P_{\ell }$, the list color function (1990); DP colorings: $P_{DP}$, the DP color function (2019), and $P_{DP}^{\ast }$, the dual DP color function (2021). For any graph $G$ and $m\in \mathbb{N}$, $P_{DP}(G,m)\le P_{\ell }(G,m)\le P(G,m)\le P_{DP}^{\ast }(G,m)$. A function $f$ is chromatic-adherent if for every graph $G$, $f(G,a)=P(G,a)$ for some $a\ge \chi (G)$ implies that $f(G,m)=P(G,m)$ for all $m\ge a$. It is not known if the list color function and the DP color function are chromatic-adherent. We show that the DP color function is not chromatic-adherent by studying the DP color function of Generalized Theta graphs. The tools we develop along with the Rearrangement Inequality give a new method for determining the DP color function of all Theta graphs and the dual DP color function of all Generalized Theta graphs.

26 pages. arXiv admin note: text overlap with arXiv:2012.12897, arXiv:2104.12268