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

Abstract

A graph $G$ is $k$-critical (list $k$-critical, DP $k$-critical) if $\chi (G)=k$ (${\chi }_{\ell }(G)=k$, ${\chi }_{\mathrm{DP}}(G)=k$) and for every proper subgraph $G^{\prime }$ of $G$, $\chi (G^{\prime })<k$ (${\chi }_{\ell }(G^{\prime })<k$, ${\chi }_{\mathrm{DP}}(G^{\prime })<k$). Let $f(n,k)$ ($f_{\ell }(n,k),f_{\mathrm{DP}}(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{DP}}(n,k)>\left(k-1+{\lceil \frac{k^2-7}{2k-7}\rceil }^{-1}\right)\frac{n}{2}.$$ This is the first bound on $f_{\mathrm{DP}}(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_{\ell }(n,k)$ than the ones known before.

23 pages