A Better Lower Bound on Average Degree of 4-List-Critical Graphs

Landon Rabern

Abstract


This short note proves that every non-complete $k$-list-critical graph has average degree at least $k-1 + \frac{k-3}{k^2-2k+2}$. This improves the best known bound for $k = 4,5,6$. The same bound holds for online $k$-list-critical graphs.

Keywords


Average degree, Critical graphs

Full Text: PDF