×

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
PDF BibTeX XML Cite