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

Original · EN

A graph G is k-critical if it has chromatic number k, but every proper subgraph of G is (k-1)--colorable. Let fₖ(n) denote the minimum number of edges in an n-vertex k-critical graph. We give a lower bound, fₖ(n) ≥ F(k,n), that is sharp for every n=1 (mod k-1). It is also sharp for k=4 and every n≥ 6. The result improves the classical bounds by Gallai and Dirac and subsequent bounds by Krivelevich and Kostochka and Stiebitz. It establishes the asymptotics of fₖ(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ₖ(n+k-1)=f(n)+k-1/2(k - 2/k-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 a graph G that satisfies |E(G[W])| < Fₖ(|W|) for all W V(G), |W| ≥ k. We also present some applications of the result.