# 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 $cr(G)$ denote the \Def[crossing number]{crossing number (graph theory)} of a graph $G$.

\begin{conjecture} Every graph $G$ with $\chi(G) \ge t$ satisfies $cr(G) \ge cr(K_t)$. \end{conjecture}

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

## Bibliography

[BT] J. Barat and G. Toth, \href[Towards the Albertson Conjecture]{http://arxiv1.library.cornell.edu/abs/0909.0413}

* indicates original appearance(s) of problem.