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

2014/06/28 by Hal Kierstead, Kierstead, Hal, Landon Rabern +1 · 1 citation
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO

paper · pdf · doi:10.48550/arxiv.1406.7355

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

arxiv created 2015/12/26 · arxiv updated 2015/12/29

Abstract

We prove that every k-list-critical graph (k ≥ 7) on n ≥ k+2 vertices has at least \frac12 (k-1 + (k-3)/((k-c)(k-1) + k-3))n edges where c = (k-3)(\frac12 - (1)/((k-1)(k-2))). 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.

Cited by

• Extracting list colorings from large independent sets

Related

• A lower bound on the number of edges in DP-critical graphs
• A better lower bound on average degree of k-list-critical graphs
• A better lower bound on average degree of 4-list-critical graphs
• A lower bound on the number of edges in DP-critical graphs. II. Four colors
• On the maximum number of edges in k-critical graphs