A better lower bound on average degree of online \(k\)-list-critical graphs (Q1753017)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A better lower bound on average degree of online \(k\)-list-critical graphs |
scientific article |
Statements
A better lower bound on average degree of online \(k\)-list-critical graphs (English)
0 references
25 May 2018
0 references
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.
0 references
list colouring
0 references
online list colouring
0 references
average degree
0 references
critical graphs
0 references
0 references