2022/02/07 by Kaul, Hemanshu, Kumar, Akash, Mudrock, Jeffrey A. +3
#05C15 #05C30 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2202.03431
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ℓ(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 ∈ ℕ such that P_ℓ(G,m) = P(G,m) whenever m ≥ k. The list color function threshold of G, denoted τ(G), is the smallest k ≥ χ(G) such that Pℓ(G,m) = P(G,m) whenever m ≥ k. In 2009, Thomassen asked whether there is a universal constant α such that for any graph G, τ(G) ≤ χℓ(G) + α, where χℓ(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 τ(K2,l) - χℓ(K2,l) ≥ C√(l) for l ≥ 16.