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)(k−1)-colorable. Let fk(n)fk(n) denote the minimum number of edges in an n-vertex k  -critical graph. We give a lower bound, fk(n)≥F(k,n)fk(n)≥F(k,n), that is sharp for every n=1(modk−1). The bound is also sharp for k=4k=4 and every n≥6n≥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 fk(n)fk(n) for every fixed k  . It also proves that the conjecture by Ore from 1967 that for every k≥4k≥4 and n≥k+2n≥k+2, fk(n+k−1)=fk(n)+k−12(k−2k−1) holds for each k≥4k≥4 for all but at most k3/12k3/12 values of n  . We give a polynomial-time algorithm for (k−1)(k−1)-coloring of a graph G   that satisfies |E(G[W])|