Cones of Theta Graphs are Enumeratively Chromatic-Choosable

Abstract

Chromatic choosability is a fundamental notion in list coloring. A graph $G$ is chromatic-choosable if its chromatic number $\chi (G)$ equals its list chromatic number ${\chi }_{\ell }(G)$. In 1990, Kostochka and Sidorenko introduced the list color function of a graph $G$, denoted by $P_{\ell }(G,m)$, which is the list-coloring analogue of its chromatic polynomial $P(G,m)$. A graph $G$ is enumeratively chromatic-choosable if $P_{\ell }(G,m)=P(G,m)$ for every $m\in \mathbb{N}$. In 2002, Ohba proved that for every graph $G$, there exists an $N\in \mathbb{N}$ such that $K_p\vee G$ is chromatic-choosable whenever $p\ge N$. Allred and Mudrock recently conjectured that an analogous statement holds for enumerative chromatic choosability. In this paper, we prove that $K_1\vee G$ is enumeratively chromatic-choosable whenever $G$ is a theta graph. Our proof combines classical inequalities, the polynomial method, and ideas from DP (or correspondence) coloring.

arXiv comment21 pages