\magnification=1200\noindent
{\bf Michael Krivelevich}\medskip\noindent
{\bf An improved bound on the minimal number of edges in color-critical
graphs}
\vskip.5cm
A graph $G$ is $k$-color-critical (or simply
 {\it $k$-critical}) if
$\chi(G)=k$ but $\chi(G')<k$ for every proper subgraph $G'$ of
$G$, where $\chi(G)$ denotes the chromatic number of $G$.
 Consider the following problem: given $k$ and $n$, what
is the minimal number of edges in a $k$-critical graph on $n$
vertices? It is easy to see that every vertex of a $k$-critical
graph $G$ has degree at least $k-1$, implying $|E(G)|\geq
{{k-1}\over {2}}|V(G)|$. Gallai improved this
trivial bound to
$|E(G)|\geq {{k-1}\over {2}}+{{k-3}\over {2(k^2-3)}}|V(G)|$
for every $k$-critical graph $G$ (where $k\geq 4$), which is not a
clique $K_k$ on $k$ vertices. In this note we strengthen
Gallai's result by showing
\medskip
\narrower\noindent
{\bf Theorem} Suppose $k\geq 4$, and let $G=(V,E)$ be a $k$-critical graph on more
than $k$ vertices. Then
$
|E(G)|\geq
({{k-1}\over {2}}+{{k-3}\over {2(k^2-2k-1)}})|V(G)|
$

\end