On the minimal number of edges in color-critical graphs (Q1272188)

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.