Shameful Inequalities for List and DP Coloring of Graphs

Abstract

The chromatic polynomial of a graph is an important notion in algebraic combinatorics that was introduced by Birkhoff in 1912; denoted $P(G,k)$, it equals the number of proper $k$-colorings of graph $G$. Enumerative analogues of the chromatic polynomial of a graph have been introduced for two well-studied generalizations of ordinary coloring, namely, list colorings: $P_{\ell }$, the list color function (1990); and DP colorings: $P_{DP}$, the DP color function (2019), and $P_{DP}^{\ast }$, the dual DP color function (2021). For any graph $G$ and $k\in \mathbb{N}$, $P_{DP}(G,k)\le P_{\ell }(G,k)\le P(G,k)\le P_{DP}^{\ast }(G,k)$. In 2000, Dong settled a conjecture of Bartels and Welsh from 1995 known as the Shameful Conjecture by proving that for any $n$-vertex graph $G$, $P(G,k+1)/(k+1{)}^n\ge P(G,k)/k^n$ for all $k\in \mathbb{N}$ satisfying $k\ge n-1$. In contrast, for infinitely many positive integers $n$, Seymour (1997) gave an example of an $n$-vertex graph for which the above inequality does not hold for some $k=\Theta (n/\log n)$. In this paper, we consider analogues of Dong's result for list and DP color functions. Specifically, in contrast to the chromatic polynomial, we prove that for any $n$-vertex graph $G$, $P_{\ell }(G,k+1)/(k+1{)}^n\ge P_{\ell }(G,k)/k^n$ and $P_{DP}(G,k+1)/(k+1{)}^n\ge P_{DP}(G,k)/k^n$ for all $k\in \mathbb{N}$. For the dual DP analogue of these inequalities, we show that there is a graph $G$ and $k\in \mathbb{N}$ such that $P_{DP}^{\ast }(G,k+1)/(k+1{)}^n<P_{DP}^{\ast }(G,k)/k^n$, and we prove $P_{DP}^{\ast }(G,k+1)/(k+1{)}^n\ge P_{DP}^{\ast }(G,k)/k^n$ for all $k\in \mathbb{N}$ satisfying $k\ge n-1$ when $G$ is an $n$-vertex complete bipartite graph.

12 pages