×

zbMATH — the first resource for mathematics

On doubly light triangles in plane graphs. (English) Zbl 1277.05047
Summary: We prove that each 3-connected plane graph of minimum degree 5 contains a triangular face of the weight at most 17 such that the sum of sizes of three its adjacent faces is at most 13. This extends theorem of Borodin on light triangles in normal plane maps. In addition, we present several related results concerning configurations of faces around a triangle in various families of plane graphs.

MSC:
05C10 Planar graphs; geometric and topological aspects of graph theory
PDF BibTeX Cite
Full Text: DOI
References:
[1] Borodin, O. V., Solution of problems of kotzig and grünbaum concerning the isolation of cycles in planar graphs, Mat. Zametki, 46, 5, 9-12, (1989) · Zbl 0694.05027
[2] Borodin, O. V., Structural properties of planar maps with the minimal degree 5, Math. Nachr., 158, 109-117, (1992) · Zbl 0776.05035
[3] Borodin, O. V., Joint extension of two theorems of kotzig on 3-polytopes, Combinatorica, 13, 1, 121-125, (1993) · Zbl 0777.05050
[4] Borodin, O. V., Structural properties of plane graphs without adjacent triangles and an application to 3-colorings, J. Graph Theory, 21, 2, 183-186, (1996) · Zbl 0838.05039
[5] Borodin, O. V., Structural theorem on plane graphs with application to the entire coloring number, J. Graph Theory, 23, 3, 233-239, (1996) · Zbl 0863.05035
[6] Borodin, O. V., Strengthening lebesgue’s theorem on the structure of the minor faces in convex polyhedra, Diskretn. Anal. Issled. Oper. Ser. 1, 9, 3, 29-39, (2002) · Zbl 1015.52008
[7] Borodin, O. V.; Sanders, D., On light edges and triangles in planar graphs of minimal degree five, Math. Nachr., 170, 19-24, (1994) · Zbl 0813.05020
[8] Diestel, R., Graph theory, (2006), Springer · Zbl 1086.05001
[9] 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
[10] Ferencová, B.; Madaras, T., On the structure of polyhedral graphs with prescribed edge and dual edge weight, Acta Univ. M. Belii Ser. Math., 12, 13-18, (2005) · Zbl 1103.05026
[11] Grünbaum, B., Polytopal graphs, MAA Stud. Math., 12, 201-224, (1975) · Zbl 0323.05104
[12] 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
[13] 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
[14] S. Jendrol’, H.-J. Voss, Light subgraphs of graphs embedded in the plane and in the projective plane—a survey, Discrete Math., in press, http://dx.doi.org/10.1016/j.disc.2012.11.007.
[15] Jendrol’, S.; Voss, H.-J., Light subgraphs of order \(\leq 3\) in large maps of minimum degree 5 on compact 2-manifolds, European J. Combin., 26, 457-471, (2005) · Zbl 1077.05029
[16] Kozáková, V.; Madaras, T., On doubly light vertices in plane graphs, Discuss. Math. Graph Theory, 31, 2, 333-344, (2011) · Zbl 1227.05132
[17] Lebesgue, H., Quelques consequences simples de la formule d’euler, J. Math. Pures Appl., 19, 19-43, (1940) · JFM 66.0736.03
[18] Madaras, T., On the structure of plane graphs of minimum face size 5, Discuss. Math. Graph Theory, 24, 3, 403-411, (2004) · Zbl 1063.05038
[19] Madaras, T., Two variations of franklin’s theorem, Tatra Mt. Math. Publ., 36, 61-70, (2007) · Zbl 1164.05013
[20] Madaras, T.; Škrekovski, R., Heavy paths, light stars and big melons, Discrete Math., 286, 115-131, (2004) · Zbl 1053.05035
[21] Madaras, T.; Škrekovski, R.; Voss, H.-J., The 7-cycle \(C_7\) is light in the family of all plane graphs with minimum degree 5, Discrete Math., 307, 1430-1435, (2007) · Zbl 1115.05022
[22] Mohar, B.; Škrekovski, R.; Voss, H.-J., Light subgraphs in planar graphs of minimum degree 4 and edge degree 9, J. Graph Theory, 44, 261-295, (2003) · Zbl 1031.05075
[23] Ore, O., (The Four-Color Problem, Pure and Applied Mathematics, vol. 27, (1967), Academic Press New York, London) · Zbl 0149.21101
[24] Sanders, D., On light edges and triangles in projective planar graphs, J. Graph Theory, 21, 3, 335-342, (1996) · Zbl 0854.05037
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.