An improved bound on the minimal number of edges in color-critical graphs (Q1379126)

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.