the plane and in the projective plane -- a survey -- |
|
Abstract: It is well known that every planar graph contains a vertex of degree at most 5. A beautiful theorem of Kotzig states that every 3-connected planar graph contains an edge whose endvertices have degree-sum at most 13. Recently, Fabrici and Jendroľ proved that every 3-connected planar graph G that contains a k-path, a path on k vertices, contains also a k-path P such that every vertex of P has degree at most 5k. A beautiful result by Enomoto and Ota says that every 3-connected planar graph G of order at least k contains a connected subgraph H of order k such that the degree sum of vertices of H in G is at most 8k-1. Motivated by these results, a concept of light graphs has been introduced. A graph k is said to be light in a class  of graphs if at least one member of contains a
copy of H and there is an integer .gif){kind=small} such that each
member G of with a copy of H also has a copy of H
with degree  .
In this paper we present a survey of results on light graphs in
different families of plane and projective plane graphs and
multigraphs. A similar survey dealing with the family of all
graphs embedded in
surfaces other than the plane and the projective plane has been
prepared as well.
Contact the authors: jendrol@kosice.upjs.sk Download PDF version of the preprint. |