Title: A lower bound on the number of edges in DP-critical graphs Show Chinese title

Title: DP-临界图中边数的下界

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'$ of $G$, $\chi(G')<k$ ($\chi_\ell(G')< k$, $\chi_\mathrm{DP}(G')<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\geq 5$ and $n\geq k+2$, then $$f_\mathrm{DP}(n,k)>\left(k - 1 + \left \lceil \frac{k^2 - 7}{2k-7} \right \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. Show Chinese abstract

Abstract: 一个图$G$是$k$-critical（列表$k$-critical，DP$k$-critical）如果$\chi(G)= k$（$\chi_\ell(G)= k$，$\chi_\mathrm{DP}(G)= k$）并且对于每个真子图$G'$of$G$，$\chi(G')<k$（$\chi_\ell(G')< k$，$\chi_\mathrm{DP}(G')<k$）。 设$f(n, k)$($f_\ell(n, k), f_\mathrm{DP}(n,k)$) 表示一个$n$顶点的$k$临界（列表$k$临界，DP$k$临界）图中的边的最小数目。 我们的主要结果是，如果$k\geq 5$且$n\geq k+2$，则$$f_\mathrm{DP}(n,k)>\left(k - 1 + \left \lceil \frac{k^2 - 7}{2k-7} \right \rceil^{-1}\right)\frac{n}{2}.$$。这是对$f_\mathrm{DP}(n,k)$的第一个渐近上界，比 Gallai 于 1963 年提出的著名的$f(n,k)$上界更优。该结果还给出了比之前已知的更优的$f_{\ell}(n,k)$上界。