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

Abstract

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)\ge F(k,n)$, that is sharp for every $n=1(\mathrm{mod}k-1)$. It is also sharp for $k=4$ and every $n\ge 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_k(n)$ for every fixed $k$. It also proves that the conjecture by Ore from 1967 that for every $k\ge 4$ and $n\ge k+2$, $f_k(n+k-1)=f(n)+\frac{k-1}{2}(k-\frac{2}{k-1})$ holds for each $k\ge 4$ for all but at most $k^3/12$ values of $n$. We give a polynomial-time algorithm for $(k-1)$-coloring a graph $G$ that satisfies $|E(G[W])|<F_k(|W|)$ for all $W\subseteq V(G)$, $|W|\ge k$. We also present some applications of the result.

Cited by in corpus (1)

• On the Minimum Edge-Density of 4-Critical Graphs of Girth Five