On the sizes of bipartite 1-planar graphs
| Autor: | Huang, Yuanqiu, Ouyang, Zhangdong, Dong, Fengming |
|---|---|
| Rok vydání: | 2020 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | 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 \u{S}krabul\'{a}kov\'{a} 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$. Comment: 20 pages, 6 figures |
| Databáze: | arXiv |
| Externí odkaz: |
|