Light subgraphs in large maps on compact 2-manifolds of minimum degree 5 .
by
Heinz-Jürgen Voss
Technical University Dresden, Germany
Coauthors: Stanislav Jendrol (Šafárik University Košice, Slovakia)

Fabrici and Jendrol' proved that each 3-connected plane graph with a path of k vertices contains a path with k vertices such that each vertex has a degree at most 5k. Such a path is said to be light. Further they showed that in the class C of all 3-connected plane graphs only the paths are light. The situation is the same in the subclass of all graphs of C with minimum degree 4. In the subclass with minimum degree 5 not only the paths but also some cycles and stars are light.

We generalized these and other results to polyhedral maps and also to more general maps on compact 2-manifolds M . Particularly, precise bounds for light paths, light stars and light cycles are obtained in several classes of maps on the 2-manifold M. Results about light subgraphs are summarized in two surveys. Here the lightness of subgraphs of order at most 5 is investigated in polyhedral maps on M of minimum degree 5 and order at least c |g(M)| , where c is an appropriate constant and g(M) is the Euler characteristic of M .

Date received: April 18, 2001