A note on the upper bounds on the size of bipartite and tripartite 1-embeddable graphs on surfaces
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.
- An annotated bibliography on 1-planarity
- An upper bound on the number of edges in an almost planar bipartite graph
- Cyclic 4-colorings of graphs on surfaces
- Ein 7-Farbensatz 1-einbettbarer Graphen auf der projektiven Ebene
- Ein Sechsfarbenproblem auf der Kugel
- Optimal 1-embedded graphs on the projective plane which triangulate other surfaces
This page was built for publication: A note on the upper bounds on the size of bipartite and tripartite 1-embeddable graphs on surfaces
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2107752)
