Crossings, colorings, and cliques (Q1028822)

Summary: \textit{M.O. Albertson} [``Chromatic number, independence ratio, and crossing number'', Ars Math. Contemp. 1, No.\,1, 1--6 (2008; Zbl 1181.05032)] 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 \textit{B. Oporowski} and \textit{D. Zhao} [``Coloring graphs with crossings'', Discrete Math. 309, No.\,9, 2948--2951 (2009; Zbl 1198.05068)]. In this paper, we prove the conjecture for \(7 \leq r \leq 12\) using results of \textit{G.A. Dirac} [``The number of edges in critical graphs'', J. Reine Angew. Math. 268/269, 150--164 (1974: Zbl 0298.05119)]; \textit{T. Gallai} [``Kritische Graphen. I and II'', Publ. Math. Inst. Hung. Acad. Sci., Ser. A 8, 165--192 (1963; Zbl 0121.18401), 373--395 (1963; Zbl 0144.23204)]; and \textit{A.V. Kostochka} and \textit{M. Stiebitz} [``Excess in colour-critical graphs'', Budapest: János Bolyai Mathematical Society. Bolyai Soc. Math. Stud. 7, 87-99 (1999; Zbl 0928.05023)] that give lower bounds on the number of edges in critical graphs, together with lower bounds by \textit{J. Pach}, \textit{R. Radoicic}, \textit{G. Tardos}, and \textit{G. Toth} [``Improving the crossing lemma by finding more crossings in sparse graphs'', Discrete Comput. Geom. 36, No.\,4, 527--552 (2006; Zbl 1104.05022)] on the crossing number of graphs in terms of the number of edges and vertices.