On the list color function threshold
Hemanshu Kaul, Akash S. Kumar, Jeffrey A. Mudrock, Patrick Rewers, Paul Shin, Khue To · Journal of Graph Theory · 2023
Abstract The chromatic polynomial of a graph , denoted , is equal to the number of proper ‐colorings of . The list color function of graph , denoted , 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 there is a such that whenever . The list color function threshold of , denoted , is the smallest such that whenever . In 2009, Thomassen asked whether there is a universal constant such that for any graph , , where is the list chromatic number of . We show that the answer to this question is no by proving that there exists a positive constant such that for .