Discrete Applied Mathematics Seminar by Jingwei Xu: A Lower Bound on the Number of Edges in DP-Critical Graphs

Speaker: Jingwei Xu, Ph.D. mathematics candidate, University of Illinois Urbana-Champaign

Title: 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 }_{DP}(G)=k)$ and for every proper subgraph $G^{\prime }$ of $G$, $\chi (G^{\prime })<k(\chi (G^{\prime })<k$, ${\chi }_{DP}(G^{\prime })<k$). Let $f(n,k)$ ($f_{\ell }(n,k),f_{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_{DP}(n,k)>(k-1+{\lceil \frac{k^2-7}{2k-7}\rceil }^{-1})\frac{n}{2}.$

This is the first bound on $f_{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.

This is joint work with Peter Bradshaw, Ilkyoo Choi, and Alexandr Kostochka

 

Discrete Applied Math Seminar

Request Zoom Link