No label defined (Q4250145)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1303523
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 1303523 |
Statements
9 January 2000
0 references
chromatic number
0 references
\(k\)-critical graph
0 references
0.9049779176712036
0 references
0.8830990195274353
0 references
0.8626723885536194
0 references
A new lower bound for the number of edges in a \(k\)-critical graph on \(n\) vertices is established. It is shown that each \(k\)-critical graph \((k\geq 4)\) has at least \((k-1)n/2+ k-3\) edges provided that \(n\geq k+2\) and \(n\neq 2k-1\). The bound is tight for \(n\in \{k+2, 2k- 2, 2k, 3k-2\}\). This improves earlier bounds due to Dirac. For the entire collection see [Zbl 0910.00036].
0 references
