scientific article; zbMATH DE number 1303523
From MaRDI portal
Publication:4250145
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].
Recommendations
Cited in
(16)- On 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
- Some remarks on \((k-1)\)-critical subgraphs of \(k\)-critical graphs
- Structure in sparse k-critical graphs
- New lower bounds on the number of edges of critical graphs
- A list version of Dirac's theorem on the number of edges in colour-critical graphs
- Minimalk-saturated and color critical graphs of prescribed minimum degree
- scientific article; zbMATH DE number 565968 (Why is no real title available?)
- Ore's conjecture on color-critical graphs is almost true
- Supersaturation problem for color-critical graphs
- On the number of edges in colour-critical graphs and hypergraphs
- Various bounds on the minimum number of arcs in a k-dicritical digraph
- On the edge-density of 4-critical graphs
- On the minimum number of arcs in \(k\)-dicritical oriented graphs
- On the maximum number of edges in k-critical graphs
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4250145)
