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'\) of \(G\), \(\chi(G')<k ( \chi(G')< k\), \(\chi _{DP}(G')<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\geq 5\) and \(n\geq k+2\), then

\(f_{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_{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