On the sizes of bipartite 1-planar graphs (Q2030739)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the sizes of bipartite 1-planar graphs |
scientific article |
Statements
On the sizes of bipartite 1-planar graphs (English)
0 references
7 June 2021
0 references
Summary: 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\geqslant 4)\) vertices and \(m\) edges. \textit{D. V. Karpov} [J. Math. Sci., New York 196, No. 6, 737--746 (2014; Zbl 1298.05087); translation from Zap. Nauchn. Sem. POMI 406, 12--30 (2012)] showed that \(m\leqslant 3n-8\) holds for even \(n\geqslant 8\) and \(m\leqslant 3n-9\) holds for odd \(n\geqslant 7\). \textit{J. Czap} et al. [Discuss. Math., Graph Theory 36, No. 1, 141--151 (2016; Zbl 1329.05081)] proved that if the partite sets of \(G\) are of sizes \(x\) and \(y\), then \(m\leqslant 2n+6x-12\) holds for \(2\leqslant x\leq y\), and conjectured that \(m\leqslant 2n+4x-12\) holds for \(x\geqslant 3\) and \(y\geqslant 6x-12\). In this paper, we settle their conjecture and our result is even under a weaker condition \(2\leqslant x\le y\).
0 references
crossing number
0 references
bipartite 1-planar graph
0 references