A note on the upper bounds on the size of bipartite and tripartite 1-embeddable graphs on surfaces (Q2107752): Difference between revisions

The authors find sharp upper bounds for the size of simple bipartite and tripartite \(1\)-embeddable graphs on closed surfaces based on the number of vertices in the graph. An associated mosaic, a graph created from an original graph by first adding the maximum number of edges without creating additional crossings and maintaining topological simplicity, and then removing all crossing edges, is considered. Euler's formula is used with the associated mosaic to establish the upper bound for the size of simply bipartite graphs. For a simple bipartite \(1\)-embeddable graph \(G\) with \(n\) vertices on a nonspherical closed surface \(F^2\), the authors find \(E(G) \leq 3n - 3\chi(F^2)\). A graph with the upper bound of edges is then constructed. The upper bound for the tripartite graph is found by uncrossing pairs of crossed edges and forming corners in the graph, and then removing one edge from each pair of multiple edges. For a simple tripartite \(1\)-embeddable graph \(G\) with \(n\) vertices on a closed surface \(F^2\), the authors find \(E(G) \leq \frac{7}{2}n - \frac{7}{2}\chi(F^2)\). Several graphs demonstrating the sharpness of the upper bound are then given.