论文标题
在列表上颜色功能阈值
On the List Color Function Threshold
论文作者
论文摘要
图$ g $的色度多项式，表示为$ p（g，m）$，等于$ g $的适当$ m $颜色的数量。图$ g $的列表颜色函数，表示为$ p _ {\ ell}（g，m）$，是自1990年代初以来已经研究的色度多项式的列表类似物，主要是通过与相应的色度多项式的比较。众所周知，对于任何图形$ g $，每当$ p_ \ ell（g，m）= p（g，m）$时，每当$ p_ \ ell（g，m）$ n he \ m athbb {n} $中都有$ k \。列表颜色函数$ g $，表示为$τ（g）$，是最小的$ k \ geqχ（g）$，因此每当$ p _ {\ ell}（g，m）= p（g，m）= p（g，m）$时，只要$ \ geq k $。在2009年，托马森（Thomassen）询问是否有一个通用常数$α$，使得对于任何图$ g $，$τ（g）\ leq \leqχ_{\ ell}（g） +α$，其中$χ_ {\ ell}（g）$是$ g $的列表元素。我们证明了这个问题的答案是没有证明存在常数的$ c $，使得$τ（k_ {2，l}） - χ_ {\ ell}（k_ {2，l}）\ ge c \ c \ sqrt {l} $ for $ l \ ge ge 16 $。
The chromatic polynomial of a graph $G$, denoted $P(G,m)$, is equal to the number of proper $m$-colorings of $G$. The list color function of graph $G$, denoted $P_{\ell}(G,m)$, is a list analogue of the chromatic polynomial that has been studied since the early 1990s, primarily through comparisons with the corresponding chromatic polynomial. It is known that for any graph $G$ there is a $k \in \mathbb{N}$ such that $P_\ell(G,m) = P(G,m)$ whenever $m \geq k$. The list color function threshold of $G$, denoted $τ(G)$, is the smallest $k \geq χ(G)$ such that $P_{\ell}(G,m) = P(G,m)$ whenever $m \geq k$. In 2009, Thomassen asked whether there is a universal constant $α$ such that for any graph $G$, $τ(G) \leq χ_{\ell}(G) + α$, where $χ_{\ell}(G)$ is the list chromatic number of $G$. We show that the answer to this question is no by proving that there exists a constant $C$ such that $τ(K_{2,l}) - χ_{\ell}(K_{2,l}) \ge C\sqrt{l}$ for $l \ge 16$.
