Progress on Albertson's Conjecture

Albertson conjectured that every graph with chromatic number $r$ has crossing number at least the crossing number of the complete graph $K_r$. This conjecture was proved for $r\le 12$ by Albertson, Cranston, and Fox; for $r\le 16$ by Barát and Tóth; and for $r\le 18$ by Ackerman. Here we verify it for $r\le 24$; we also greatly restrict the possibilities for counterexamples when $r\in \{25,26\}$. In addition, we strengthen earlier work bounding the order of a minimum counterexample for each choice of $r$: we exclude the possibility that $\mathrm{\mid }G\mathrm{\mid }\ge 2.82r$ and exclude the possibility that $1.228r\le \mathrm{\mid }G\mathrm{\mid }\le 1.768r$. Finally, as $r$ grows, we extend the lower end of this range of excluded orders for a minimum counterexample. In particular: if $r\ge \mathrm{125,000}$, then we exclude the possibility that $1.10r\le \mathrm{\mid }G\mathrm{\mid }\le 1.768r$; and if $r\ge \mathrm{825,000}$, then we exclude the possibility that $1.05r\le \mathrm{\mid }G\mathrm{\mid }\le 1.768r$.