论文标题
$ p（g，l）-p（g，k）$ $ k $ - 分配$ l $的改进的下限
An improved lower bound of $P(G, L)-P(G,k)$ for $k$-assignments $L$
论文作者
论文摘要
令$ g =（v，e）$是一个简单的图形，带有$ n $顶点和$ m $边缘，$ p（g，k）$是$ g $的色度多项式，$ g $，$ p（g，l）$是$ l $ l $ g $的$ g $的数量，用于任何$ k $ k $ assignment $ l $ l $。在本文中，我们表明，当$ k \ ge m-1 \ ge 3 $，$ p（g，l）-p（g，k）$下面以$ \ left（（（k-m+1）k^{n-3}+\ frac {（k-m+3） e} | l（u）\ setMinus l（v）| $，其中$ c \ ge \ frac {（m-1）（m-3）（m-3）} {8} $，尤其是，如果$ g $是$ k_3 $ -free，则$ k_3 $ -free，则$ c \ ge {m-c \ ge {m-c \ ge {m-2} +2} +2} +2 \ 2 \ sqrt m-3 $。因此，只要$ k \ ge m-1 $，$ p（g，l）\ ge p（g，k）$。
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$.
