A lower bound on the number of edges in DP-critical graphs

A graph $G$ is $k$-critical (list $k$-critical, DP $k$-critical) if $\chi (G)=k$ (${\chi }_{\mathrm{\ell }}(G)=k$, ${\chi }_{\mathrm{D}\mathrm{P}}(G)=k$) and for every proper subgraph $G^{\mathrm{\prime }}$ of $G$, $\chi (G^{\mathrm{\prime }})<k$ (${\chi }_{\mathrm{\ell }}(G^{\mathrm{\prime }})<k$, ${\chi }_{\mathrm{D}\mathrm{P}}(G^{\mathrm{\prime }})<k$). Let $f(n,k)$ ($f_{\mathrm{\ell }}(n,k),f_{\mathrm{D}\mathrm{P}}(n,k)$) denote the minimum number of edges in an $n$-vertex $k$-critical (list $k$-critical, DP $k$-critical) graph. Our main result is that if $k\ge 5$ and $n\ge k+2$, then $$f_{\mathrm{D}\mathrm{P}}(n,k)>(k-1+{\lceil \frac{k^2-7}{2k-7}\rceil }^{-1})\frac{n}{2}\mathrm{.}$$ This is the first bound on $f_{\mathrm{D}\mathrm{P}}(n,k)$ that is asymptotically better than the well-known bound on $f(n,k)$ by Gallai from 1963. The result also yields a slightly better bound on $f_{\mathrm{\ell }}(n,k)$ than the ones known before.