Crossings, colorings, and cliques

Abstract

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\le r\le 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 et.al. on the crossing number of graphs in terms of the number of edges and vertices.

15 pages