学术文献库

The chromatic polynomial of a graph $G$, denoted $P(G,m)$, is equal to the number of proper $m$-colorings of $G$ for each $m \in \mathbb{N}$. In 1990, Kostochka and Sidorenko introduced the list color function of graph $G$, denoted $P_{\ell}(G,m)$, which is a list analogue of the chromatic polynomial. 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$. It is known that for every graph $G$, $τ(G)$ is finite, and in fact, $τ(G) \leq (|E(G)|-1)/\ln(1+ \sqrt{2}) + 1$. It is also known that when $G$ is a cycle or chordal graph, $G$ is enumeratively chromatic-choosable which means $τ(G) = χ(G)$. A recent paper of Kaul et al. suggests that understanding the list color function threshold of complete bipartite graphs is essential to the study of the extremal behavior of $τ$. In this paper we show that for any $n \geq 2$, $τ(K_{2,n}) \leq \lceil (n+2.05)/1.24 \rceil$ which gives an improvement on the general upper bound for $τ(G)$ when $G = K_{2,n}$. We also develop additional tools that allow us to show that $τ(K_{2,3}) = χ(K_{2,3})$ and $τ(K_{2,4}) = τ(K_{2,5}) = 3$.