A local epsilon version of Reed's Conjecture

In 1998, Reed conjectured that every graph $G$ satisfies $\chi(G) \leq \lceil \frac{1}{2}(\Delta(G) + 1 + \omega(G))\rceil$,where$\chi(G)$ is the chromatic number of $G$, $\mathrm{\Delta }(G)$ is the maximum degree of $G$, and $\omega (G)$ is the clique number of $G$. As evidence for his conjecture, he proved an “epsilon version” of it, i.e. that there exists some $\epsilon >0$ such that $\chi (G)\le (1-\epsilon )(\mathrm{\Delta }(G)+1)+\epsilon \omega (G)$. It is natural to ask if Reed’s conjecture or an epsilon version of it is true for the list-chromatic number. In this paper we consider a “local version” of the list-coloring version of Reed’s conjecture. Namely, we conjecture that if $G$ is a graph with list-assignment $L$ such that for each vertex $v$ of $G$, $\mathrm{\mid }L(v)\mathrm{\mid }\ge \lceil \frac{1}{2}(d(v)+1+\omega (v))\rceil$, where $d(v)$ is the degree of $v$ and $\omega (v)$ is the size of the largest clique containing $v$, then $G$ is $L$-colorable. Our main result is that an “epsilon version” of this conjecture is true, under some mild assumptions. Using this result, we also prove a significantly improved lower bound on the density of $k$-critical graphs with clique number less than $k\mathrm{/}2$, as follows. For every $\alpha >0$, if $\epsilon \le \frac{{\alpha }^2}{1350}$, then if $G$ is an $L$-critical graph for some $k$-list-assignment $L$ such that $\omega (G)<(\frac{1}{2}-\alpha )k$ and $k$ is sufficiently large, then $G$ has average degree at least $(1+\epsilon )k$. This implies that for every $\alpha >0$, there exists $\epsilon >0$ such that if $G$ is a graph with $\omega (G)\le (\frac{1}{2}-\alpha )\mathrm{m}\mathrm{a}\mathrm{d}(G)$, where $\mathrm{m}\mathrm{a}\mathrm{d}(G)$ is the maximum average degree of $G$, then $\chi_\ell(G) \leq \left\lceil (1 - \varepsilon)($\mathrm{m}\mathrm{a}\mathrm{d}$(G) + 1) + \varepsilon \omega(G)\right\rceil$.