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

MaRDI QIDQ1753017zbMATH OpenFDO

Authors Landon Rabern

Publication date 25 May 2018

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1608.06989, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i1p51

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

average degreecritical graphslist colouringonline list colouring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Abstract: We improve the best known bounds on average degree of $k$-list-critical graphs for $kge6$. Specifically, for $kge7$ we show that every non-complete $k$-list-critical graph has average degree at least $k-1+frac(k-3{)}^2(2k-3)k^4-2k^3-11k^2+28k-14$ and every non-complete $6$-list-critical graph has average degree at least $5+frac93766$. The same bounds hold for online $k$-list-critical graphs.

Review text

Summary: We improve the best known bounds on average degree of online \(k\)-list-critical graphs for \(k \geqslant 6\). Specifically, for \(k \geqslant 7\) we show that every non-complete online \(k\)-list-critical graph has average degree at least \(k-1 + \frac{(k-3)^2 (2 k-3)}{k^4-2 k^3-11 k^2+28 k-14}\) and every non-complete online \(6\)-list-critical graph has average degree at least \(5 + \frac{93}{766}\). The same bounds hold for offline \(k\)-list-critical graphs.

Recommendations

• Improved lower bounds on the number of edges in list critical and online list critical graphs
• A better lower bound on average degree of 4-list-critical graphs
• Maximum average degree of list-edge-critical graphs and Vizing's conjecture
• Edge lower bounds for list critical graphs, via discharging
• Total list weighting of graphs with bounded maximum average degree
• On the average degree of edge chromatic critical graphs
• Faster exponential-time algorithms in graphs of bounded average degree
• Faster exponential-time algorithms in graphs of bounded average degree
• Lower bound of the Hadwiger number of graphs by their average degree
• scientific article; zbMATH DE number 1383105

Cites work

• A better lower bound on average degree of 4-list-critical graphs
• A new lower bound on the number of edges in colour-critical graphs and hypergraphs
• Edge lower bounds for list critical graphs, via discharging
• Extracting List colorings from large independent sets
• Graph theory
• scientific article; zbMATH DE number 3735847 (Why is no real title available?)
• scientific article; zbMATH DE number 3195967 (Why is no real title available?)
• Improved lower bounds on the number of edges in list critical and online list critical graphs
• Independence, odd girth, and average degree
• Mr. Paint and Mrs. Correct
• Ore's conjecture on color-critical graphs is almost true

Cited in

(4)

• Improved lower bounds on the number of edges in list critical and online list critical graphs
• A better lower bound on average degree of 4-list-critical graphs
• On the density of critical graphs with no large cliques
• A lower bound on the number of edges in DP-critical graphs

This page was built for publication: A better lower bound on average degree of online \(k\)-list-critical graphs

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