Towards The Albertson Conjecture

Abstract

Albertson conjectured that if a graph $G$ has chromatic number $r$ then its crossing number is at least as much as the crossing number of $K_r$. Albertson, Cranston, and Fox verified the conjecture for $r\le 12$. We prove the statement for $r\le 16$.

13 pages, 4 figures

References in corpus (2)

• Improved bounds for the crossing numbers of K_m,n and K_n
• Coloring graphs with crossings