1Department of Mathematics, Hunan Normal University, 410081 Changsha, China 2Department of Mathematics, Hunan First Normal University 3National Institute of Education, Nanyang Technological University, Singapore
The electronic journal of combinatorics, Tome 28 (2021) no. 2
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$ ($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, Przybyło and Škrabul'á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$.
1
Department of Mathematics, Hunan Normal University, 410081 Changsha, China
2
Department of Mathematics, Hunan First Normal University
3
National Institute of Education, Nanyang Technological University, Singapore
@article{10_37236_10012,
author = {Yuanqiu Huang and Zhangdong Ouyang and Fengming Dong},
title = {On the sizes of bipartite 1-planar graphs},
journal = {The electronic journal of combinatorics},
year = {2021},
volume = {28},
number = {2},
doi = {10.37236/10012},
zbl = {1465.05048},
url = {http://geodesic.mathdoc.fr/articles/10.37236/10012/}
}
TY - JOUR
AU - Yuanqiu Huang
AU - Zhangdong Ouyang
AU - Fengming Dong
TI - On the sizes of bipartite 1-planar graphs
JO - The electronic journal of combinatorics
PY - 2021
VL - 28
IS - 2
UR - http://geodesic.mathdoc.fr/articles/10.37236/10012/
DO - 10.37236/10012
ID - 10_37236_10012
ER -
%0 Journal Article
%A Yuanqiu Huang
%A Zhangdong Ouyang
%A Fengming Dong
%T On the sizes of bipartite 1-planar graphs
%J The electronic journal of combinatorics
%D 2021
%V 28
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/10012/
%R 10.37236/10012
%F 10_37236_10012
Yuanqiu Huang; Zhangdong Ouyang; Fengming Dong. On the sizes of bipartite 1-planar graphs. The electronic journal of combinatorics, Tome 28 (2021) no. 2. doi: 10.37236/10012
