Towards the Albertson Conjecture

János Barát, Géza Tóth

Abstract


Albertson conjectured that if a graph $G$ has chromatic number $r$, then the crossing number of $G$ is at least as large as the crossing number of $K_r$, the complete graph on $r$ vertices. Albertson, Cranston, and Fox verified the conjecture for $r\le 12$. In this paper we prove it for $r\le 16$.


Full Text: PDF