Towards the Albertson Conjecture

  • János Barát
  • Géza Tóth
DOI: https://doi.org/10.37236/345

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$.

Published
2010-05-14
Issue
Volume 17 (2010)
Article Number
R73