Crossing numbers and coloring

Importance: High ✭✭✭
Recomm. for undergrads: no
Posted by: mdevos
on: September 4th, 2009

We let $ cr(G) $ denote the crossing number of a graph $ G $.

Conjecture   Every graph $ G $ with $ \chi(G) \ge t $ satisfies $ cr(G) \ge cr(K_t) $.

This conjecture is an interesting weakening of the disproved Hajos Conjecture which asserted that $ \chi(G) \ge t $ implies that $ G $ contains a subdivision of $ K_t $.

A minimal counterexample to Albertson's conjecture is critical, with minimum degree $ \ge t $. Using this and the crossing lemma, Albertson, Cranston and Fox showed that a minimum counterexample has at most $ 4t $ vertices. They then analyzed small cases to show that the conjecture holds for $ t \le 12 $. More recently, Barat and Toth [BT] sharpened these arguments to show that the conjecture holds for $ t \le 16 $.


[BT] J. Barat and G. Toth, Towards the Albertson Conjecture

* indicates original appearance(s) of problem.