crossing number

Graph Theory » Topological G.T. » Crossing numbers

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

Problem Does the following equality hold for every graph $G$ ? $\text{pair-cr}(G) = \text{cr}(G)$

The crossing number $\text{cr}(G)$ of a graph $G$ is the minimum number of edge crossings in any drawing of $G$ in the plane. In the pairwise crossing number $\text{pair-cr}(G)$ , we minimize the number of pairs of edges that cross.

Keywords: crossing number; pair-crossing number

Posted by cibulka
updated November 3rd, 2009

add new comment

Graph Theory » Topological G.T. » Crossing numbers

Crossing numbers and coloring ★★★

Author(s): Albertson

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

Keywords: coloring; complete graph; crossing number

Posted by mdevos
updated September 4th, 2009

add new comment

Graph Theory » Topological G.T. » Crossing numbers

Crossing sequences ★★

Author(s): Archdeacon; Bonnington; Siran

Conjecture Let $(a_0,a_1,a_2,\ldots,0)$ be a sequence of nonnegative integers which strictly decreases until $0$ .

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

Keywords: crossing number; crossing sequence

Posted by Robert Samal
updated July 30th, 2008

add new comment

Graph Theory » Topological G.T. » Coloring

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

Author(s): Oporowski; Zhao

For a graph $G$ , we let $cr(G)$ denote the crossing number of $G$ , and we let $\omega(G)$ denote the size of the largest complete subgraph of $G$ .

Question Does every graph $G$ with $cr(G) \le 5$ and $\omega(G) \le 5$ have a 5-coloring?

Keywords: coloring; crossing number; planar graph

Posted by mdevos
updated October 9th, 2007

add new comment

Graph Theory » Topological G.T. » Crossing numbers

Drawing disconnected graphs on surfaces ★★

Author(s): DeVos; Mohar; Samal

Conjecture Let $G$ be the disjoint union of the graphs $G_1$ and $G_2$ and let $\Sigma$ be a surface. Is it true that every optimal drawing of $G$ on $\Sigma$ has the property that $G_1$ and $G_2$ are disjoint?

Keywords: crossing number; surface

Posted by mdevos
updated September 30th, 2007

1 comment

Graph Theory » Topological G.T. » Crossing numbers

The Crossing Number of the Hypercube ★★

Author(s): Erdos; Guy

The crossing number $cr(G)$ of $G$ is the minimum number of crossings in all drawings of $G$ in the plane.

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