Crossing numbers and coloring
We let denote the crossing number of a graph .
This conjecture is an interesting weakening of the disproved Hajos Conjecture which asserted that implies that contains a subdivision of .
A minimal counterexample to Albertson's conjecture is critical, with minimum degree . Using this and the crossing lemma, Albertson, Cranston and Fox showed that a minimum counterexample has at most vertices. They then analyzed small cases to show that the conjecture holds for . More recently, Barat and Toth [BT] sharpened these arguments to show that the conjecture holds for .
[BT] J. Barat and G. Toth, Towards the Albertson Conjecture
* indicates original appearance(s) of problem.