Home » Subject » Graph Theory » Topological G.T. » Crossing numbers

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

Bibliography

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


* indicates original appearance(s) of problem.
add new comment