Ore's conjecture on color-critical graphs is almost true

A graph G is k-critical if it has chromatic number k, but every proper subgraph of G is (k-1)-colorable. Let f_k(n) denote the minimum number of edges in an n-vertex k-critical graph. We give a lower bound, f_k(n)≥F(k, n), that is sharp for every n=1(modk-1). The bound is also sharp for k=4 and every n≥6. The result improves a bound by Gallai and subsequent bounds by Krivelevich and Kostochka and Stiebitz, and settles the corresponding conjecture by Gallai from 1963. It establishes the asymptotics of f_k(n) for every fixed k. It also proves that the conjecture by Ore from 1967 that for every k≥4 and n≥k+2, fk(n+k-1)=fk(n)+k-12(k-2k-1) holds for each k≥4 for all but at most k³/12 values of n. We give a polynomial-time algorithm for (k-1)-coloring of a graph G that satisfies |E(G[W])|<F(k, |W|) for all W⊆V(G), |W|≥k. We also present some applications of the result.