Jendrol’, S.; Voss, H. J. Light paths with an odd number of vertices in polyhedral maps. (English) Zbl 1079.05502 Czech. Math. J. 50, No. 3, 555-564 (2000). Summary: Let \(P_k\) be a path on \(k\) vertices. In an earlier paper we have proved that each polyhedral map \(G\) on any compact \(2\)-manifold \(\mathbb M\) with Euler characteristic \(\chi (\mathbb M)\leq 0\) contains a path \(P_k\) such that each vertex of this path has, in \(G\), degree \(\leq k\lfloor A \rfloor \) with \(2A = 5+ \sqrt {49-24\chi (\mathbb M)}\). Moreover, this bound is attained for \(k=1\) or \(k\geq 2\), \(k\) even. In this paper we prove that for each odd \(k\geq \frac 43 \lfloor A\rfloor +1\), this bound is the best possible on infinitely many compact \(2\)-manifolds, but on infinitely many other compact \(2\)-manifolds the upper bound can be lowered to \(\lfloor (k-\frac 13)A\rfloor \). Cited in 1 Document MSC: 05C10 Planar graphs; geometric and topological aspects of graph theory 05C38 Paths and cycles 52B10 Three-dimensional polytopes Keywords:graphs; path; polyhedral map; embeddings PDFBibTeX XMLCite \textit{S. Jendrol'} and \textit{H. J. Voss}, Czech. Math. J. 50, No. 3, 555--564 (2000; Zbl 1079.05502) Full Text: DOI EuDML References: [1] I. Fabrici, S. Jendroľ: Subgraphs with restricted degrees of their vertices in planar \(3\)-connected graphs. Graphs Combin. 13 (1997), 245-250. · Zbl 0891.05025 · doi:10.1007/BF03353001 [2] B. Grünbaum, G. C. Shephard: Analogues for tiling of Kotzig’s theorem on minimal weights of edges. Ann. Discrete Math. 12 (1982), 129-140. · Zbl 0504.05026 · doi:10.1016/S0304-0208(08)73499-6 [3] J. Ivančo: The weight of a graph. Ann. Discrete Math. 51 (1992), 113-116. · Zbl 0773.05066 · doi:10.1016/S0167-5060(08)70614-9 [4] S. Jendroľ: Paths with restricted degrees of their vertices in planar graphs. Czechoslovak Math. J. 49 (124) (1999), 481-490. · Zbl 1003.05055 · doi:10.1023/A:1022411100562 [5] S. Jendroľ, H.-J. Voss: A local property of polyhedral maps on compact \(2\)-dimensional manifolds. Discrete Math. 212 (2000), 111-120. · Zbl 0946.05029 · doi:10.1016/S0012-365X(99)00329-5 [6] S. Jendroľ, H.-J. Voss: Light paths with an odd number of vertices in large polyhedral maps. Ann. Comb. 2 (1998), 313-324. · Zbl 0929.05049 · doi:10.1007/BF01608528 [7] M. Jungerman: Ph. D. Thesis. Univ. of California. Santa Cruz, California 1974. [8] A. Kotzig: Contribution to the theory of Eulerian polyhedra. Math. Čas. SAV (Math. Slovaca) 5 (1955), 111-113. [9] A. Kotzig: Extremal polyhedral graphs. Ann. New York Acad. Sci. 319 (1979), 569-570. [10] G. Ringel: Map Color Theorem. Springer-Verlag Berlin (1974). · Zbl 0287.05102 [11] J. Zaks: Extending Kotzig’s theorem. Israel J. Math. 45 (1983), 281-296. · Zbl 0524.05031 · doi:10.1007/BF02804013 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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.