crossing number


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

Author(s): Pach; Tóth

\begin{problem} Does the following equality hold for every graph $G$? \[ \text{pair-cr}(G) = \text{cr}(G) \] \end{problem}

The \Def[crossing number]{Crossing number (graph theory)} $\text{cr}(G)$ of a graph $G$ is the minimum number of edge crossings in any drawing of $G$ in the plane. In the \emph{pairwise crossing number} $\text{pair-cr}(G)$, we minimize the number of pairs of edges that cross. %and the \emph{odd-crossing number} $(\text{odd-cr}(G))$ counts the minimum %number of pairs of edges that cross an odd number of times.

Keywords: crossing number; pair-crossing number

Crossing numbers and coloring ★★★

Author(s): Albertson

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}

Keywords: coloring; complete graph; crossing number

Crossing sequences ★★

Author(s): Archdeacon; Bonnington; Siran

\begin{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. \end{conjecture}

Keywords: crossing number; crossing sequence

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

Author(s): Oporowski; Zhao

For a graph $G$, we let $cr(G)$ denote the \Def[crossing number]{Crossing number (graph theory)} of $G$, and we let $\omega(G)$ denote the size of the largest complete subgraph of $G$.

\begin{question} Does every graph $G$ with $cr(G) \le 5$ and $\omega(G) \le 5$ have a 5-coloring? \end{question}

Keywords: coloring; crossing number; planar graph

Drawing disconnected graphs on surfaces ★★

Author(s): DeVos; Mohar; Samal

\begin{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? \end{conjecture}

Keywords: crossing number; surface

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.

\begin{conjecture} $\displaystyle \lim \frac{cr(Q_d)}{4^d} = \frac{5}{32}$ \end{conjecture}

Keywords: crossing number; hypercube

The Crossing Number of the Complete Bipartite Graph ★★★

Author(s): Turan

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

\begin{conjecture} $\displaystyle cr(K_{m,n}) = \floor{\frac m2} \floor{\frac {m-1}2} \floor{\frac n2} \floor{\frac {n-1}2} $ \end{conjecture}

Keywords: complete bipartite graph; crossing number

The Crossing Number of the Complete Graph ★★★

Author(s):

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

\begin{conjecture} $\displaystyle cr(K_n) = \frac 14 \floor{\frac n2} \floor{\frac{n-1}2} \floor{\frac{n-2}2} \floor{\frac{n-3}2}$ \end{conjecture}

Keywords: complete graph; crossing number

Syndicate content