{"id":"arxiv/2608.06757","url":"https://arxiv.org/abs/2608.06757","tags":["math.CO"],"score":0,"title":"Density of list- and correspondence-critical graphs","domain":"math.CO","source":"arxiv","authors":["Peter Bradshaw"],"reviews":0,"subject":"math.CO","summary":"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) = \\liminf_{n \\rightarrow \\infty} \\frac 2n (f_{\\ell}(n,k) - k + 1)$. We show that for all $k \\geq 4$ and $n \\geq k+2$, every list $k$-critical graph on $n \\geq k+2$ vertices has more than $(k-1+\\frac 1{28}) \\frac n2$ edges, which implies that $g_{\\ell}(k) \\geq \\frac{1}{28}$ for all $k \\geq 4$. This…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-08-07","reactions":{}}