zbMATH — the first resource for mathematics

The structure of 1-planar graphs. (English) Zbl 1111.05026
Summary: A graph is called 1-planar if it can be drawn in the plane so that each of its edges is crossed by at most one other edge. In the paper, we study the existence of subgraphs of bounded degrees in 1-planar graphs. It is shown that each 1-planar graph contains a vertex of degree at most 7; we also prove that each 3-connected 1-planar graph contains an edge with both endvertices of degree at most 20, and we present similar results concerning bigger structures in 1-planar graphs with additional constraints.

05C10 Planar graphs; geometric and topological aspects of graph theory
Full Text: DOI
[1] Borodin, O.V., Solution of Ringel’s problems on the vertex-face coloring of plane graphs and on the coloring of 1-planar graphs, Diskret. anal. Novosibirsk, 41, 12-26, (1984), (in Russian) · Zbl 0565.05027
[2] Borodin, O.V., Solution of problems of kotzig and grünbaum concerning the isolation of cycles in planar graphs, Mat. zametki, 46, 9-12, (1989) · Zbl 0694.05027
[3] Borodin, O.V.; Kostochka, A.V.; Raspaud, A.; Sopena, E., Acyclic colouring of 1-planar graphs, Discrete anal. oper. res., 6, 4, 20-35, (1999) · Zbl 0931.05032
[4] Fabrici, I.; Hexel, E.; Jendrol’, S.; Walther, H., On vertex-degree restricted paths in polyhedral graphs, Discrete math., 212, 61-73, (2000) · Zbl 0946.05047
[5] Fabrici, I.; Jendrol’, S., Subgraphs with restricted degrees of their vertices in planar 3-connected graphs, Graphs combin., 13, 245-250, (1997) · Zbl 0891.05025
[6] Franklin, P., The four color problem, Amer. J. math., 44, 225-236, (1922) · JFM 48.0664.02
[7] Harant, J.; Jendrol’, S.; Tkáč, M., On 3-connected plane graphs without triangular faces, J. combin. theory ser. B, 77, 150-161, (1999) · Zbl 1027.05030
[8] Jendrol’, S.; Madaras, T., On light subgraphs in plane graphs of minimum degree five, Discuss. math. graph theory, 16, 207-217, (1996) · Zbl 0877.05050
[9] Jendrol’, S.; Madaras, T.; Soták, R.; Tuza, Z., On light cycles in plane triangulations, Discrete math., 197/198, 453-467, (1999) · Zbl 0936.05065
[10] S. Jendrol’, H.-J. Voss, Light subgraphs of graphs embedded in 2-dimensional manifolds of Euler characteristic \(\leqslant 0\): a survey, in: G. Halász et al. (Eds.), Paul Erdös and his Mathematics II, Based on the Conference, Budapest, Hungary, July 4-11, 1999, Springer, Berlin, Bolyai Soc. Math. Stud. 11, 2002, pp. 375-411. · Zbl 1037.05015
[11] S. Jendrol’, H.-J. Voss, Light subgraphs of graphs embedded in plane and in the projective plane: a survey, Discrete Math., submitted for publication. · Zbl 1259.05045
[12] Jendrol’, S.; Owens, P., On light subgraphs in 3-connected plane graphs without triangular or quadrangular faces, Graphs combin., 17, 659-680, (2001) · Zbl 0988.05031
[13] E. Jucovič, Konvexné mnohosteny, Veda, Bratislava 1981.
[14] Kotzig, A., Contribution to the theory of Eulerian polyhedra, Mat. čas. SAV (math. slovaca), 5, 111-113, (1955)
[15] Lebesgue, H., Quelques consequences simples de la formule d’euler, J. math. pures appl., 19, 19-43, (1940) · JFM 66.0736.03
[16] Madaras, T.; Škrekovski, R., Heavy paths, Light stars and big melons, discrete math., 286, 115-131, (2004) · Zbl 1053.05035
[17] Ringel, G., Ein sechsfarbenproblem auf der kugel, Abh. math. sem. univ. Hamburg, 29, 107-117, (1965) · Zbl 0132.20701
[18] Wernicke, P., Über den kartographischen vierfarbensatz, Math. ann., 58, 413-426, (1904) · JFM 35.0511.01
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.