zbMATH — the first resource for mathematics

On \(3\)-connected plane graphs without triangular faces. (English) Zbl 1027.05030
Summary: We prove that each polyhedral triangular face-free map \(G\) on a compact 2-dimensional manifold \(\mathbb{M}\) with Euler characteristics \(\chi(\mathbb{M})\) contains a \(k\)-path, i.e., a path on \(k\) vertices, such that each vertex of this path has, in \(G\), degree at most \((5/2)k\) if \(\mathbb{M}\) is a sphere \(\mathbb{S}_0\) and at most \((k/2)\lfloor(5+ \sqrt{49-24\chi(\mathbb{M})})/2\rfloor\) if \(\mathbb{M}\neq \mathbb{S}_0\) or does not contain any \(k\)-path. We show that for even \(k\) this bound is best possible. Moreover, we show that for any graph other than a path no similar estimation exists.

05C10 Planar graphs; geometric and topological aspects of graph theory
05C38 Paths and cycles
Full Text: DOI
[1] Ando, K.; Iwasaki, S.; Kaneko, A., Every 3-connected planar graph has a connected subgraph with small degree sum, Annual meeting in mathematical society of Japan, (1993)
[2] Barnette, D., Trees in polyhedral graphs, Canad. J. math., 18, 731-736, (1966) · Zbl 0141.21401
[3] Barnette, D., 2-connected spanning subgraphs of planar 3-connected graphs, J. combin. theory ser. B, 61, 210-216, (1994) · Zbl 0812.05015
[4] Borodin, O.V., Minimal vertex degree sum of a 3-path in plane maps, Discuss. math. graph theory, 17, 279-284, (1997) · Zbl 0906.05017
[5] Cromwell, P.R., Polyhedra, (1997), Cambridge Univ. Press Cambridge
[6] I. Fabrici, E. Hexel, S. Jendrol’, and, H. Walther, On vertex-degree restricted paths in polyhedral graphs, to appear in, Discrete Math. · Zbl 0946.05047
[7] 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
[8] Fabrici, I.; Jendrol’, S., Subgraphs with restricted degrees of their vertices in planar graphs, Discrete math., 191, 83-90, (1998) · Zbl 0956.05059
[9] Franklin, P., The four colour problem, (), 225-236 · JFM 48.0664.02
[10] Gao, Z., 2-connected coverings of bounded degree in 3-connected graphs, J. graph theory, 20, 327-338, (1995) · Zbl 0838.05034
[11] Grünbaum, B., Polytopal graphs, MAA stud. math., 12, 201-224, (1975) · Zbl 0323.05104
[12] Jendrol’, S., A structural property of convex 3-polytopes, Geom. dedicata, 68, 91-99, (1997) · Zbl 0893.52007
[13] 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
[14] 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
[15] S. Jendrol’, and, P. J. Owens, On light graphs in polyhedral graphs without triangular and quadrangular faces, submitted for publication. · Zbl 0988.05031
[16] S. Jendrol’, and, J.-J. Voss, A local property of polyhedral maps on compact 2-dimensional manifolds, submitted for publication. · Zbl 0933.05044
[17] Kotzig, A., Contribution to the theory of Eulerian polyhedra, Math. slovaca, 5, 111-113, (1955)
[18] Mohar, B., Face-width of embedded graphs, Math. slovaca, 47, 35-63, (1997) · Zbl 0958.05034
[19] Lebesgue, H., Quelques conséquences simples de la formule d’Euler, J. math. pures appl., 19, 27-43, (1940) · JFM 66.0736.03
[20] Robertson, N.; Vitray, R.P., Representativity of surface embeddings, (), 293-328 · Zbl 0735.05032
[21] Sachs, H., Einführung in die theorie der endlichen graphen, (1972), Teubner Leipzig
[22] Thomassen, C., Tilings of the torus and the Klein bottle and vertex-transitive graphs on a fixed surface, Amer. math. soc., 323, 605-635, (1991) · Zbl 0722.05031
[23] 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.