A better lower bound on average degree of k-list-critical graphs

2016/08/24 by Landon Rabern, Rabern, Landon
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Interconnection Networks and Systems #Limits and Structures in Graph Theory #math.CO

paper · pdf · doi:10.48550/arxiv.1608.06989

arxiv created 2016/08/24 · openalex publication_date 2016/08/24 · arxiv updated 2016/08/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We improve the best known bounds on average degree of k-list-critical graphs for k ≥ 6. Specifically, for k ≥ 7 we show that every non-complete k-list-critical graph has average degree at least k-1 + ((k-3)² (2 k-3))/(k⁴-2 k³-11 k²+28 k-14) and every non-complete 6-list-critical graph has average degree at least 5 + (93)/(766). The same bounds hold for online k-list-critical graphs.

Related

• A better lower bound on average degree of 4-list-critical graphs
• Improved lower bounds on the number of edges in list critical and online list critical graphs
• A lower bound on the number of edges in DP-critical graphs
• The average degree of edge chromatic critical graphs with maximum degree seven
• Average degrees of edge-chromatic critical graphs