An improved lower bound of $P(G,L)-P(G,k)$ for $k$-assignments $L$

Abstract

Let $G=(V,E)$ be a simple graph with $n$ vertices and $m$ edges, $P(G,k)$ be the chromatic polynomial of $G$, and $P(G,L)$ be the number of $L$-colorings of $G$ for any $k$-assignment $L$. In this article, we show that when $k\ge m-1\ge 3$, $P(G,L)-P(G,k)$ is bounded below by $\left((k-m+1)k^{n-3}+\frac{(k-m+3)c}{3}{k}^{n-5}\right)\sum _{uv\in E}|L(u)\setminus L(v)|$, where $c\ge \frac{(m-1)(m-3)}{8}$, and in particular, if $G$ is $K_3$-free, then $c\ge \left(\genfrac{}{}{0ex}{}{m-2}{2}\right)+2\sqrt{m}-3$. Consequently, $P(G,L)\ge P(G,k)$ whenever $k\ge m-1$.

12 pages