# Crossing numbers and coloring

 Importance: High ✭✭✭
 Author(s): Albertson, Michael O.
 Subject: Graph Theory » Topological Graph Theory » » Crossing numbers
 Keywords: coloring complete graph crossing number
 Posted by: mdevos on: September 4th, 2009

We let denote the crossing number of a graph .

Conjecture   Every graph with satisfies .

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 .

## Bibliography

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

* indicates original appearance(s) of problem.