Density of list- and correspondence-critical graphs

Abstract

A graph $G$ is list $k$-critical if $G$ is not $(k-1)$-list-colorable, but every proper subgraph of $G$ is $(k-1)$-list-colorable. In this paper, we study the function $f_{\ell }(n,k)$ denoting the minimum number of edges in an $n$-vertex list $k$-critical graph, as well as the function $g_{\ell }(k)={\mathrm{liminf}}_{n\to \infty }\frac{2}{n}(f_{\ell }(n,k)-k+1)$. We show that for all $k\ge 4$ and $n\ge k+2$, every list $k$-critical graph on $n\ge k+2$ vertices has more than $(k-1+\frac{1}{28})\frac{n}{2}$ edges, which implies that $g_{\ell }(k)\ge \frac{1}{28}$ for all $k\ge 4$. This is the first result showing that ${\mathrm{liminf}}_{k\to \infty }{g}_{\ell }(k)>0$. We also show that $g_{\ell }(k)\ge \frac{1}{24}$ for all $k\ge 352$. As a corollary to our result, we obtain the following improvement to Brooks' theorem: For all $d\ge 3$, if $G$ has no $K_{d+1}$ subgraph and has maximum average degree at most $d+\frac{1}{28}$, then $G$ is $d$-list-colorable. All of our results hold in the setting of correspondence coloring (DP-coloring) as well. As a corollary of our correspondence coloring result, we also show that for each $d\ge 3$, a minimal unsatisfiable anti-functional constraint satisfaction problem (CSP) with variable domains of size $d$ has a primal graph either containing $K_{d+1}$ or with average degree at least $d+\frac{1}{28}$.

arXiv comment16 pages