论文标题
关键图的交叉数的新上限
New upper bounds for the crossing numbers of crossing-critical graphs
论文作者
论文摘要
如果$ cr（g）\ ge k $，则图$ g $是{$ k $ -crossing-Crication-Crication}，但是$ cr（g \ setMinus e）<k $ in E（g）$中的每个边缘$ e \ g $，其中$ cr（g）$是$ g $的交叉数。众所周知，对于任何$ k $ - 杂交的图形$ g $，$ cr（g）\ le 2.5k+16 $持有，尤其是$δ（g）\ ge 4 $，则$ cr（g）\ le 2k+35 $ holds，$δ（g）$是$ g $的最低学位。在本文中，我们将这些上限提高到$ 2.5K +2.5美元和$ 2K +8 $。特别是，对于任何$ k $ - 杂交图$ g $，带有$ n $顶点，如果$δ（g）\ ge 5 $，则$ cr（g）\ le 2k- \ sqrt k/2n+35/6 $持有。
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.
