% A LaTeX file for a 3 page document
%
%
\title
{An improved bound on the minimal number of edges in color-critical
graphs}
\author{Michael Krivelevich
\thanks{e-mail: mkrivel@math.ias.edu}
\\School of Mathematics,\\
Institute for Advanced Study, Princeton, NJ 08540, USA.\\
{\bf AMS Subject Classification:} 05C15, 05C35.\\
Submitted: June 26, 1997. Accepted: November 24, 1997.
} 
\date{}

\documentstyle[12pt]{article}

\hsize=6in
\vsize=9in

\oddsidemargin  0pt     %   Left margin on odd-numbered pages.
\evensidemargin 0pt     %   Left margin on even-numbered pages.
\marginparwidth 40pt    %   Width of marginal notes.
\marginparsep 10pt      % Horizontal space between outer margin and
                        % marginal note


% VERTICAL SPACING:
\topmargin 0pt           % Nominal distance from top of page to top of
                         %    box containing running head.
\headsep 10pt            %    Space between running head and text.


% DIMENSION OF TEXT:

\textheight 8.4in      %Height of text(including footnotes and figures,
                         % excluding running head and foot).
\textwidth 6.5in         % Width of text line.
\renewcommand{\baselinestretch}{1.3}
\topmargin 0pt
\headsep 10pt

\pagestyle{myheadings}
\markright{\sc the electronic journal of combinatorics 1 (1998),
\#R4\hfill}
\thispagestyle{empty}

\begin{document}
\bibliographystyle{plain}
\maketitle
\setcounter{page}{1}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}

\begin{abstract}
It is proven that for $k\geq 4$ and $n>k$ every $k$-color-critical
graph on $n$ vertices has at least
$\left(\frac{k-1}{2}+\frac{k-3}{2(k^2-2k-1)}\right)n$ edges, thus
improving a result of Gallai from 1963.
\end{abstract}


A graph $G$ is $k$-color-critical (or simply {\em $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$. (See,
e.g., \cite{JT} for a detailed account of graph coloring
problems). 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
\frac{k-1}{2}|V(G)|$. Gallai \cite{G} improved this
trivial bound to
$|E(G)|\geq\left(\frac{k-1}{2}+\frac{k-3}{2(k^2-3)}\right)|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
\begin{theorem}\label{theor1}
Suppose $k\geq 4$, and let $G=(V,E)$ be a $k$-critical graph on more
than $k$ vertices. Then
\[
|E(G)|\geq
\left(\frac{k-1}{2}+\frac{k-3}{2(k^2-2k-1)}\right)|V(G)|\ .
\]
\end{theorem}
In the first non-trivial case $k=4$ we get $|E(G)|\geq
\frac{11}{7}|V(G)|$, compared to the estimate
$|E(G)|\geq \frac{20}{13}|V(G)|$ of Gallai.

Let us introduce some definitions and notation (we follow the
terminology of \cite{SS}). If $G=(V,E)$ is a $k$-critical graph, then
the {\em low-vertex subgraph} of $G$, denoted by $L(G)$,
is the subgraph of $G$, induced by all vertices of degree $k-1$.
The {\em high-vertex subgraph} of $G$, which we denote by $H(G)$,
 is the subgraph of $G$ induced by all vertices of
degree at least $k$ in $G$. Brooks' theorem implies that if 
$k\geq 4$ and $G\neq K_k$, then  $H(G)\neq \emptyset$.
A maximal by inclusion connected subgraph $B$ of a graph $G$ such
that every two edges of $B$ are contained in a cycle of $G$ is
called a {\em block} of $G$. A connected graph all of whose
blocks are either complete graphs or odd cycles is called a {\em
Gallai tree}, a {\em Gallai forest} is a graph all of whose
connected components are Gallai trees. A {\em $k$-Gallai forest
(tree)} is a Gallai forest (tree), in which all vertices have
degree at most $k-1$.

Our proof utilizes results of Gallai \cite{G} and Stiebitz \cite{S},
describing the structure of color-critical graphs. Gallai proved
the following fundamental result.

\begin{lemma}[\cite{G}, Satz E.1]\label{lemma1} If $G$ is a
$k$-critical graph then its low-vertex subgraph $L(G)$ is a
$k$-Gallai forest (possibly empty).
\end{lemma}
Using induction on the number of vertices, it follows from the
above statement that
\begin{lemma}[\cite{G}, Lemma 4.5]\label{lemma2}
Let $k\geq 4$. Let $G=(V,E)\neq K_k$ be a $k$-Gallai forest. Then
\begin{equation}\label{lb1}
|E(G)|\leq \left(\frac{k-2}{2}+\frac{1}{k-1}\right)|V(G)|-1\ .
\end{equation}
\end{lemma}

The second ingredient of our proof is the following result of
Stiebitz.
\begin{lemma}[\cite{S}]\label{lemma3}
Let $G$ be a $k$-critical graph containing at least one vertex of
degree $k-1$. Then the number of connected
components of its high-vertex subgraph $H(G)$ does not exceed the
number of connected components of its low-vertex subgraph $L(G)$.
\end{lemma}

\noindent{\bf Proof of Theorem \ref{theor1}.}\ \ Let $L(G)$ and
$H(G)$ be the low-vertex and the high-vertex subgraphs of $G$,
respectively. Denote $n_L=|V(L(G))|$, $n_H=|V(H(G))|$,
$n=|V(G)|=n_L+n_H$. By Brooks' theorem $n_H>0$. Also, if
$V(L(G))=\emptyset$, we are done, therefore we may assume that
$n_L>0$.

Let $r$ be the number of connected components of $H(G)$, then
trivially
\begin{equation}\label{lb2}
|E(H(G))|\geq n_H-r\ .
\end{equation}
Also, by Lemma \ref{lemma3}, the number of connected components of
$L(G)$ is at least $r$. Now the crucial observation is that each
connected component of $L(G)$ is itself a $k$-Gallai tree, therefore
the estimate (\ref{lb1}) is valid for it too. We infer that
\begin{equation}\label{lb3}
|E(L(G))|\leq
\left(\frac{k-2}{2}+\frac{1}{k-1}\right)n_L-r\ .
\end{equation}
Indeed, if $G_1=(V_1,E_1),\ldots,G_{r'}=(V_{r'},E_{r'})$ are the
connected components of $L(G')$, where $r'\geq r$, then by Lemma
\ref{lemma1}
\[
|E_i|\leq \left(\frac{k-2}{2}+\frac{1}{k-1}\right)|V_i|-1\,,
\quad i=1,\ldots,r'\,.
\]
Summing the above inequalities over $1\leq i\leq r'$, we get
(\ref{lb3}).

Using (\ref{lb2}) and (\ref{lb3}), the number of edges of $G$ can
be bounded from below as follows:
\begin{eqnarray}
|E(G)| &=& \sum_{v\in V(L(G))}d(v)-|E(L(G))|+|E(H(G))|\nonumber\\
       &\geq& (k-1)n_L-\left(\frac{k-2}{2}+\frac{1}{k-1}\right)n_L
               +r+n_H-r\nonumber\\
       &=& n +\frac{k^2-3k}{2(k-1)}\, n_L\ .\label{lb4}
\end{eqnarray}
On the other hand, it follows from the definition of $L(G)$ and
$H(G)$ that
\begin{eqnarray}
|E(G)| &=& \frac 12\sum_{v\in V(G)}d(v)=\frac 12\left(\sum_{v\in
V(L(G))}d(v)+\sum_{v\in V(H(G))}d(v)\right)\nonumber\\
       &\geq& \frac 12 ((k-1)n_L+kn_H)=\frac k2 n-\frac 12 n_L\ .
       \label{lb5}
\end{eqnarray}
Multiplying (\ref{lb5}) by $(k^2-3k)/(k-1)$ and summing with
(\ref{lb4}) we get
\[
\left(1+\frac{k^2-3k}{k-1}\right)|E(G)| \geq 
\left(1+\frac k2\, \frac{k^2-3k}{k-1}\right)n\ ,
\]
or
\[
|E(G)| \geq \left(\frac{k-1}{2}+\frac{k-3}{2(k^2-2k-1)}\right)n\ ,
\]
as claimed.\quad\quad$\Box$

\bigskip

A more detailed treatment of the problem, containing
lower and upper bounds on the minimal number of edges in a
$k$-critical graph on $n$ vertices with additional restrictions
imposed, and some applications of these bounds to Ramsey-type
problems and problems on random graphs, will appear in a
forthcoming paper \cite{K}.


\begin{thebibliography}{9}
\bibitem{G} T. Gallai, {\em Kritische Graphen I}, Publ. Math.
Inst. Hungar. Acad. Sci. 8 (1963), 265--292.
\bibitem{JT} T. R. Jensen and B. Toft, {\bf Graph coloring
problems}, Wiley, New York, 1995.
\bibitem{K} M. Krivelevich, {\em On the minimal number of edges in
color-critical graphs}, Combinatorica, to appear.
\bibitem{SS} H. Sachs and M. Stiebitz, {\em Colour-critical graphs
with vertices of low valency}, Annals of Discrete Math. 41 (1989),
371--396.
\bibitem{S} M. Stiebitz, {\em Proof of a conjecture of T. Gallai
concerning connectivity properties of colour-critical graphs},
Combinatorica 2 (1982), 315--323.
\end{thebibliography}
\end{document}