Krivelevich, Michael An improved bound on the minimal number of edges in color-critical graphs. (English) Zbl 0885.05063 Electron. J. Comb. 5, Research paper R4, 4 p. (1998); printed version J. Comb. 5, 61-64 (1998). Summary: It is proven that for \(k\geq 4\) and \(n>k\) every \(k\)-color-critical graph on \(n\) vertices has at least \(\left(\frac{k-1}{2}+\frac{k-3}{2(k^2-2k-1)}\right)n\) edges, thus improving a result of Gallai from 1963. Cited in 6 Documents MSC: 05C15 Coloring of graphs and hypergraphs 05C35 Extremal problems in graph theory PDFBibTeX XMLCite \textit{M. Krivelevich}, Electron. J. Comb. 5, No. 1, Research paper R4, 4 p. (1998; Zbl 0885.05063) Full Text: EuDML EMIS