Compare DP color functions with chromatic polynomials
Fengming Dong, Yan Yang · arXiv (Cornell University) · 2021
For any graph $G$, the chromatic polynomial of $G$ is the function $P(G,m)$ which counts the number of proper $m$-colorings of $G$ for each positive integer $m$. The DP color function $P_{DP}(G,m)$ of $G$, introduced by Dvořak and Postle in 2018, is a generalization of $P(G,m)$ with $P_{DP}(G,m)\le P(G,m)$ for each positive integer $m$. Let $P_{DP}(G)\approx P(G)$ denote the property that $P_{DP}(G,m)=P(G,m)$ holds for sufficiently large integers $m$. Kaul and Mudrock have showed that there are graphs $G$ for which $P_{DP}(G)\approx P(G)$ holds and there are also graphs $G$ for which $P_{DP}(G,m)<P(G,m)$ for sufficiently large integers $m$. In this article, we give a necessary condition and a sufficient condition for $P_{DP}(G)\approx P(G)$ to be true. For each edge $e$ in $G$, let $\ell(e)=\infty$ if $e$ is a bridge of $G$, and let $\ell(e)$ be the length of a shortest cycle in $G$ containing $e$ otherwise. We first show that if $P_{DP}(G)\approx P(G)$, then $\ell(e)$ is not even for each edge $e$ in $G$. We then prove that $P_{DP}(G)\approx P(G)$ holds for every graph $G$ which contains a spanning tree $T$ such that for each $e\in E(G)\setminus E(T)$, $\ell(e)$ is odd and $e$ is contained in a cycle $C$ of length $\ell (e)$ with the property that $\ell(e')<\ell(e)$ for each $e'\in E(C)\setminus (E(T)\cup \{e\})$. This result generalizes a recent result due to Mudrock and Thomason that $P_{DP}(G)\approx P(G)$ holds for each graph $G$ which has a dominating vertex.