New upper bounds for the crossing numbers of crossing-critical graphs

A graph $G$ is {$k$-crossing-critical} if $cr(G)\ge k$, but $cr(G\setminus e)<k$ for each edge $e\in E(G)$, where $cr(G)$ is the crossing number of $G$. It is known that for any $k$-crossing-critical graph $G$, $cr(G)\le 2.5k+16$ holds, and in particular, if $δ(G)\ge 4$, then $cr(G)\le 2k+35$ holds, where $δ(G)$ is the minimum degree of $G$. In this paper, we improve these upper bounds to $2.5k +2.5$ and $2k+8$ respectively. In particular, for any $k$-crossing-critical graph $G$ with $n$ vertices, if $δ(G)\ge 5$, then $cr(G)\le 2k-\sqrt k/2n+35/6$ holds.

No reviews yet.

No comments yet.