\magnification=1200
\hsize=4in
\overfullrule=0pt
\input amssym
%\def\frac#1 #2 {{#1\over #2}}
\def\emph#1{{\it #1}}
\def\em{\it}
\nopagenumbers
\noindent
%
%
{\bf Michael O. Albertson, Daniel W. Cranston and Jacob Fox}
%
%
\medskip
\noindent
%
%
{\bf Crossings, Colorings, and Cliques}
%
%
\vskip 5mm
\noindent
%
%
%
%
Albertson conjectured that if graph $G$ has chromatic number $r$, then
the crossing number of $G$ is at least that of the complete graph
$K_r$. This conjecture in the case $r=5$ is equivalent to the four
color theorem. It was verified for $r=6$ by Oporowski and Zhao.  In
this paper, we prove the conjecture for $7 \leq r \leq 12$ using
results of Dirac; Gallai; and Kostochka and Stiebitz that give lower
bounds on the number of edges in critical graphs, together with lower
bounds by Pach {\it et al.} on the crossing number of graphs in terms
of the number of edges and vertices.



\bye