DMGT

Article in volume

Authors:

H. Shibuya

Hikari Shibuya

xxx

Y. Suzuki

Yusuke Suzuki

Tsuruoka National College of Technology, Tsuruoka, Yamagat

Title:

A note on the upper bounds on the size of bipartite and tripartite 1-embeddable graphs on surfaces

Source:

Discussiones Mathematicae Graph Theory 43(1) (2023) 171-177

Received: 2020-02-17 , Revised: 2020-08-05 , Accepted: 2020-08-06 , Available online: 2020-09-24 , https://doi.org/10.7151/dmgt.2361

Abstract:

In this note, we show sharp upper bounds of the size of simple bipartite and tripartite $1$-embeddable graphs on closed surfaces.

Keywords:

$1$-embedding, bipartite graph, tripartite graph

References:

D.V. Karpov, An upper bound on the number of edges in an almost planar bipartite graphs, J. Math. Sci. 196 (2014) 737–746.
https://doi.org/10.1007/s10958-014-1690-9
S.G. Kobourov, G. Liotta and F. Montecchiani, An annotated bibliography on $1$-planarity, Comput. Sci. Rev. 25 (2017) 49–67.
https://doi.org/10.1016/j.cosrev.2017.06.002
A. Nakamoto, K. Noguchi and K. Ozeki, Cyclic $4$-colorings of graphs on surfaces, J. Graph Theory 82 (2016) 265–278.
https://doi.org/10.1002/jgt.21900
T. Nagasawa, K. Noguchi and Y. Suzuki, Optimal $1$-embedded graphs which triangulate other surfaces, J. Nonlinear Convex Anal. 19 (2018) 1759–1770.
G. Ringel, Ein Sechsfarbenproblem auf der Kugel, Abh. Math. Semin. Univ. Hambg. 29 (1965) 107–117.
https://doi.org/10.1007/BF02996313
H. Von Schumacher, Ein $7$-Farbensatz $1$-einbettbarer Graphen auf der projektiven Ebene, Abh. Math. Semin. Univ. Hambg. 54 (1984) 5–14.
https://doi.org/10.1007/BF02941434