Crossing numbers and coloring

Importance: High ✭✭✭
Recomm. for undergrads: no
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.