论文标题
在两部分1平面图的尺寸上
On the sizes of bipartite 1-planar graphs
论文作者
论文摘要
如果该图被称为$ 1 $ - 平面，则该图在平面中录制了图纸，以使每个边缘最多一次越过。令$ g $为$ n $（$ \ ge 4 $）顶点和$ m $边缘的两部分1平面图。卡尔波夫（Karpov）表明，$ m \ le 3n-8 $持有，即使$ n \ ge 8 $和$ m \ le 3n-9 $持有奇数$ n \ ge 7 $。 Czap, Przybylo and uSkrabuláková proved that if the partite sets of $G$ are of sizes $x$ and $y$, then $m\le 2n+6x-12$ holds for $2\leq x\leq y$, and conjectured that $m\le 2n+4x-12$ holds for $x\ge 3$ and $y\ge 6x-12$.在本文中，我们解决了他们的猜想，我们的结果甚至处于较弱的$ 2 \ le x \ le y $的情况下。
A graph is called $1$-planar if it admits a drawing in the plane such that each edge is crossed at most once. Let $G$ be a bipartite 1-planar graph with $n$ ($\ge 4$) vertices and $m$ edges. Karpov showed that $m\le 3n-8$ holds for even $n\ge 8$ and $m\le 3n-9$ holds for odd $n\ge 7$. Czap, Przybylo and uSkrabuláková proved that if the partite sets of $G$ are of sizes $x$ and $y$, then $m\le 2n+6x-12$ holds for $2\leq x\leq y$, and conjectured that $m\le 2n+4x-12$ holds for $x\ge 3$ and $y\ge 6x-12$. In this paper, we settle their conjecture and our result is even under a weaker condition $2\le x\le y$.
