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

DOI10.1016/J.JCTB.2019.05.004MaRDI QIDQ2284728zbMATH OpenOpenAlexWikidataFDO

Authors Landon Rabern, H. A. Kierstead

Publication date 15 January 2020

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1406.7355

zbMATH Keywords

critical graphlist coloringonline list coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Abstract: We prove that every $k$-list-critical graph ($kge7$) on $ngek+2$ vertices has at least $frac12left(k-1+frack-3(k-c)(k-1)+k-3ight)n$ edges where $c=(k-3)left(frac12-frac1(k-1)(k-2)ight)$. 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.

Recommendations

• A better lower bound on average degree of online \(k\)-list-critical graphs
• A new lower bound on the number of edges in colour-critical graphs and hypergraphs
• New lower bounds on the number of edges of critical graphs
• A better lower bound on average degree of 4-list-critical graphs
• Edge lower bounds for list critical graphs, via discharging

Cites work

• \(\Delta \)-critical graphs with small high vertex cliques
• A new lower bound on the number of edges in colour-critical graphs and hypergraphs
• A Theorem of R. L. Brooks and a Conjecture of H. Hadwiger
• Brooks' theorem via the Alon-Tarsi theorem
• Colorings and orientations of graphs
• Critically paintable, choosable or colorable graphs
• Flexible color lists in Alon and Tarsi's theorem, and time scheduling with unreliable participants
• Graphs with chromatic number close to maximum degree
• scientific article; zbMATH DE number 3735847 (Why is no real title available?)
• scientific article; zbMATH DE number 3563170 (Why is no real title available?)
• scientific article; zbMATH DE number 3195967 (Why is no real title available?)
• scientific article; zbMATH DE number 3043302 (Why is no real title available?)
• Mr. Paint and Mrs. Correct
• Note on the colouring of graphs
• On the minimal number of edges in color-critical graphs
• On-line list colouring of graphs
• Ore-type versions of Brooks' theorem
• Ore's conjecture for k=4 and Grötzsch's theorem
• Ore's conjecture on color-critical graphs is almost true

Cited in

(8)

• Edge lower bounds for list critical graphs, via discharging
• A better lower bound on average degree of online \(k\)-list-critical graphs
• A better lower bound on average degree of 4-list-critical graphs
• On the minimum edge-density of 5-critical triangle-free graphs
• Generalized DP-colorings of graphs
• Special issue in honour of Landon Rabern
• Characterizing 4-critical graphs with Ore-degree at most seven
• A lower bound on the number of edges in DP-critical graphs

This page was built for publication: Improved lower bounds on the number of edges in list critical and online list critical graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2284728)