A lower bound on the number of edges in DP-critical graphs. II. Four colors

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. The main result of this paper is that if $n\ge 6$ and $n\notin \{7,10\}$, then $$f_{\mathrm{DP}}(n,4)>\left(3+\frac{1}{5}\right)\frac{n}{2}.$$ This is the first bound on $f_{\mathrm{DP}}(n,4)$ that is asymptotically better than the well-known bound $f(n,4)\ge \left(3+\frac{1}{13}\right)\frac{n}{2}$ by Gallai from 1963. The result also yields a better bound on $f_{\ell }(n,4)$ than the one known before.

23 pages. arXiv admin note: substantial text overlap with arXiv:2409.00937