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 (mod k - 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, f(k)(n + k - 1) = f(k)(n) + k - 1/2 (k - 2/k-1) holds for each k >= 4 for all but at most k(3)/12 values of n. We give a polynomial-time algorithm for (k - 1)-coloring of a graph G that satisfies vertical bar E(G[W])vertical bar < F(k, vertical bar W vertical bar) for all W subset of V(G), vertical bar W vertical bar >= k. We also present some applications of the result. Published by Elsevier Inc.