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
    0 references
    0 references
    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

    Identifiers