Math Conjectures

Albertson's Crossing-Number Conjecture

OPENMajorConjectureProposed 2007 · Standard version

Canonical statement

Every finite simple graph GG satisfies
cr⁡(G)≥cr⁡ ⁣(Kχ(G)). \operatorname{cr}(G)\geq \operatorname{cr}\!\left(K_{\chi(G)}\right).
Here cr⁡(G)\operatorname{cr}(G) is the minimum number of edge crossings in a plane drawing of GG, χ(G)\chi(G) is its chromatic number, and KqK_q is the complete graph on qq vertices.
View source LaTeX
Every finite simple graph \(G\) satisfies
\[
  \operatorname{cr}(G)\geq
  \operatorname{cr}\!\left(K_{\chi(G)}\right).
\]
Here \(\operatorname{cr}(G)\) is the minimum number of edge crossings in
a plane drawing of \(G\), \(\chi(G)\) is its chromatic number, and \(K_q\)
is the complete graph on \(q\) vertices.
GRAPH-014:[Albertson2007Crossing][BaratToth2010Albertson][Cranston2025Albertson]
Graph theoryGeometry and topology

Notes

Albertson's conjecture ties together two graph parameters of very different character: it asserts that every finite simple graph GG satisfies cr⁡(G)≥cr⁡(Kχ(G))\operatorname{cr}(G)\geq\operatorname{cr}(K_{\chi(G)}), so that among all graphs of a given chromatic number the complete graph has the smallest crossing number. Michael Albertson posed the conjecture in 2007 [Albertson2007Crossing]. For χ(G)≤4\chi(G)\leq 4 the claim is trivial since cr⁡(K4)=0\operatorname{cr}(K_4)=0, while the case χ(G)=5\chi(G)=5 amounts to the Four Color Theorem, since it says precisely that planar graphs are 44-colorable.

Barát and Tóth verified the conjecture for all graphs of small chromatic number [BaratToth2010Albertson], and subsequent work has extended the range of χ\chi covered and treated dense and minor-rich regimes where crossing numbers can be bounded from below effectively [Cranston2025Albertson].

Beyond bounded chromatic number, however, neither a proof valid for all χ\chi nor a counterexample is known, and the conjecture remains open.

References (3)

The boxed statement is the canonical open formulation — not a stronger variant or a related research program. The status reflects the catalog's last review; do your own literature search before investing serious effort.