# crossing number

## Are different notions of the crossing number the same? ★★★

**Problem**Does the following equality hold for every graph ?

The crossing number of a graph is the minimum number of edge crossings in any drawing of in the plane. In the *pairwise crossing number* , we minimize the number of pairs of edges that cross.

Keywords: crossing number; pair-crossing number

## Crossing numbers and coloring ★★★

Author(s): Albertson

We let denote the crossing number of a graph .

**Conjecture**Every graph with satisfies .

Keywords: coloring; complete graph; crossing number

## Crossing sequences ★★

Author(s): Archdeacon; Bonnington; Siran

**Conjecture**Let be a sequence of nonnegative integers which strictly decreases until .

Then there exists a graph that be drawn on a surface with orientable (nonorientable, resp.) genus with crossings, but not with less crossings.

Keywords: crossing number; crossing sequence

## 5-coloring graphs with small crossing & clique numbers ★★

For a graph , we let denote the crossing number of , and we let denote the size of the largest complete subgraph of .

**Question**Does every graph with and have a 5-coloring?

Keywords: coloring; crossing number; planar graph

## Drawing disconnected graphs on surfaces ★★

Author(s): DeVos; Mohar; Samal

**Conjecture**Let be the disjoint union of the graphs and and let be a surface. Is it true that every optimal drawing of on has the property that and are disjoint?

Keywords: crossing number; surface

## The Crossing Number of the Hypercube ★★

The crossing number of is the minimum number of crossings in all drawings of in the plane.

The -dimensional (hyper)cube is the graph whose vertices are all binary sequences of length , and two of the sequences are adjacent in if they differ in precisely one coordinate.

**Conjecture**

Keywords: crossing number; hypercube

## The Crossing Number of the Complete Bipartite Graph ★★★

Author(s): Turan

The crossing number of is the minimum number of crossings in all drawings of in the plane.

**Conjecture**

Keywords: complete bipartite graph; crossing number

## The Crossing Number of the Complete Graph ★★★

Author(s):

The crossing number of is the minimum number of crossings in all drawings of in the plane.

**Conjecture**

Keywords: complete graph; crossing number