Improved lower bounds on the number of edges in list critical and online list critical graphs

Abstract

We prove that every $k$-list-critical graph ($k\ge 7$) on $n\ge k+2$ vertices has at least $\frac{1}{2}\left(k-1+\frac{k-3}{(k-c)(k-1)+k-3}\right)n$ edges where $c=(k-3)\left(\frac{1}{2}-\frac{1}{(k-1)(k-2)}\right)$. This improves the bound established by Kostochka and Stiebitz. The same bound holds for online $k$-list-critical graphs, improving the bound established by Riasat and Schauz. Both bounds follow from a more general result stating that either a graph has many edges or it has an Alon-Tarsi orientable induced subgraph satisfying a certain degree condition.

arXiv commentThis paper has been split in half. This is the first half, the second half is "Extracting list colorings from large independent sets"