  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)
\geq F(k,n)$, that is sharp for every $n=1 ({\rm mod} k-1)$. It is also sharp
for $k=4$ and every $n\geq 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\geq 4$ and
$n\geq k+2$, $f_k(n+k-1)=f(n)+\frac{k-1}{2}(k - \frac{2}{k-1})$ holds for each
$k\geq 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| \geq k$. We also present some
applications of the result.
