Speaker: Peter Bradshaw (UIUC)

Title: On the number of edges in DP-critical graphs

Abstract: A graph G is DP k-critical if G has correspondence chromatic number k, and every proper subgraph of G has correspondence chromatic number at most k-1. In this talk, we show that every DP 4-critical graph on at least 11 vertices has average degree more than 3.2. We show that this lower bound holds for list 4-critical graphs as well, which improves a result of Rabern. We also obtain lower bounds for the number of edges in DP k-critical graphs for k ≥ 5. In particular, every DP 5-critical graph on at least 7 vertices has average degree more than 5 + 1/6, and every DP 6-critical graph on at least 8 vertices has average degree more than 6 + 1/6.

This is joint work with Ilkyoo Choi, Alexandr Kostochka, and Jingwei Xu.