Enumerative Chromatic Choosability

Chromatic-choosability is a notion of fundamental importance in list coloring. A graph is chromatic-choosable when its chromatic number is equal to its list chromatic number. In 1990, Kostochka and Sidorenko introduced the list color function of a graph G, denoted P_(G,m), which is the list analogue of the chromatic polynomial of G, $P(G,m)$. It is known that for any graph G there is a positive integer k such that P_(G,m) = P(G,m) whenever m ≥ k. In this paper, we study enumerative chromatic-choosability. A graph G is enumeratively chromatic-choosable when P_(G,m) = P(G,m) whenever m ∈ N. We completely determine the graphs of chromatic number two that are enumeratively chromatic-choosable. We construct examples of graphs that are chromatic-choosable but fail to be enumeratively chromatic-choosable, and finally, we explore a conjecture as to whether for every graph G, there is a p ∈ N such that the join of G and Kₚ is enumeratively chromatic-choosable. The techniques we use to prove results are diverse and include probabilistic ideas and ideas from DP (or correspondence)-coloring.