zbMATH — the first resource for mathematics

Light subgraphs of graphs embedded in 2-dimensional manifolds of Euler characteristic $$\leq 0$$: A survey. (English) Zbl 1037.05015
Halász, Gábor (ed.) et al., Paul Erdős and his mathematics II. Based on the conference, Budapest, Hungary, July 4–11, 1999. Berlin: Springer (ISBN 3-540-42236-6/2-vol. set; 963-8022-96-5). Bolyai Soc. Math. Stud. 11, 375-411 (2002).
An old result of Kotzig says that each planar 3-connected graph has an edge whose degree sum is at most 13. This is the prototype of the concept of a ‘light’ subgraph: A subgraph $$H$$ is light in a class $${\mathcal G}$$ of graphs if each graph $$G\in{\mathcal G}$$ that contains $$H$$ at all, also contains a copy of $$H$$ for which the degree sum of the vertices of $$G$$ that are part of that subgraph is bounded. This property depends on the graph and the class, so the $$K_2$$ is by Kotzig’s theorem light in the class of 3-connected planar graphs, but the graph $$K_{2,n}$$ shows that it is not light in the class of 2-connected planar graphs. In this paper the authors survey results of this type for graph classes defined by embedding properties into 2-dimensional manifolds.
For the entire collection see [Zbl 0999.00016].

MSC:
 05C10 Planar graphs; geometric and topological aspects of graph theory
Keywords:
Kotzig’s theorem; small degree sum