zbMATH — the first resource for mathematics

A local property of large polyhedral maps on compact 2-dimensional manifolds. (English) Zbl 0933.05044
Summary: We prove that each polyhedral map \(G\) on a compact 2-manifold, which has large enough vertices, contains a \(k\)-path, a path on \(k\) vertices, such that each vertex of it has, in \(G\), degree at most \(6k\); this bound being best possible for \(k\) even. Moreover, if \(G\) has large enough vertices of degree \(>6k\), than it contains a \(k\)-path such that each of its vertices has degree, in \(G\), at most \(5k\); this bound is best possible for any \(k\).

05C10 Planar graphs; geometric and topological aspects of graph theory
05C35 Extremal problems in graph theory
05C38 Paths and cycles
54C25 Embedding
Full Text: DOI