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\limits_{ 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 { m-2\choose 2}+2\sqrt m-3$. Consequently, $P(G,L)\ge P(G,k)$ whenever $k\ge m-1$.
Categories: math.CO