On the minimal number of edges in color-critical graphs (Q1272188)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the minimal number of edges in color-critical graphs |
scientific article |
Statements
On the minimal number of edges in color-critical graphs (English)
0 references
24 November 1998
0 references
Given a critical \(k\)-chromatic graph with \(e\) edges, \(n\) vertices, and no \((s+1)\)-clique (\(3\leq s<k\)), the inequalities \(e\geq ({k\over 2} -{k-2 \over{2(2k-s-3)}})n\) (for \(s\leq {2k \over 3}\)) and \(e\geq ({k\over 2} -{{(k-2)s\over {2(2ks-2k-s^2)}}})n\) (for \(s\geq {2k \over 3}\)) hold. For \(s=k-1\) this improves the earlier estimate \(e\geq ({k-1 \over 2}+{k-3 \over {2(k^2-3)}})n\) of Gallai.
0 references
extremal graph theory
0 references
chromatic critical graphs
0 references
0 references