%0 Generic %1 kaul2022color %A Kaul, Hemanshu %A Kumar, Akash %A Mudrock, Jeffrey A. %A Rewers, Patrick %A Shin, Paul %A To, Khue %D 2022 %K graph_polynomial graphs list_colouring %T On the List Color Function Threshold %U http://arxiv.org/abs/2202.03431 %X 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 N$ such that $P_\ell(G,m) = P(G,m)$ whenever $m k$. The list color function threshold of $G$, denoted $\tau(G)$, is the smallest $k \chi(G)$ such that $P_\ell(G,m) = P(G,m)$ whenever $m k$. In 2009, Thomassen asked whether there is a universal constant $\alpha$ such that for any graph $G$, $\tau(G) \chi_\ell(G) + \alpha$, where $\chi_\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 $\tau(K_2,l) - \chi_\ell(K_2,l) Cl$ for $l 16$.

@misc{kaul2022color, abstract = {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 $\tau(G)$, is the smallest $k \geq \chi(G)$ such that $P_{\ell}(G,m) = P(G,m)$ whenever $m \geq k$. In 2009, Thomassen asked whether there is a universal constant $\alpha$ such that for any graph $G$, $\tau(G) \leq \chi_{\ell}(G) + \alpha$, where $\chi_{\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 $\tau(K_{2,l}) - \chi_{\ell}(K_{2,l}) \ge C\sqrt{l}$ for $l \ge 16$.}, added-at = {2022-02-09T14:56:51.000+0100}, author = {Kaul, Hemanshu and Kumar, Akash and Mudrock, Jeffrey A. and Rewers, Patrick and Shin, Paul and To, Khue}, biburl = {https://www.bibsonomy.org/bibtex/2b53c8110f1912e252e56cf1f3bdb6bdd/j.c.m.janssen}, description = {On the List Color Function Threshold}, interhash = {2674a4520c7910eb4f51f11b10942c5e}, intrahash = {b53c8110f1912e252e56cf1f3bdb6bdd}, keywords = {graph_polynomial graphs list_colouring}, note = {cite arxiv:2202.03431Comment: 11 pages}, timestamp = {2022-02-09T14:56:51.000+0100}, title = {On the List Color Function Threshold}, url = {http://arxiv.org/abs/2202.03431}, year = 2022 }