##
**Zentralblatt MATH**

**Publications of (and about) Paul Erdös**

**Zbl.No: ** 405.05031

**Autor: ** Erdös, Paul; Hajnal, András

**Title: ** On spanned subgraphs of graphs. (In English)

**Source: ** Beiträge zur Graphentheorie und deren Anwendungen, vorgetr. auf dem int. Kolloq., Oberhof (DDR) 1977, 80-96 (1977).

**Review: ** [For the entire collection see Zbl 387.00005.]

In this paper, theorems of the following type are proved: Let C be a class of (finite) graphs satisfying certain asymptotic conditions saying that for G in C, both G and its complement \overline G are large. Then for all G in C and all H in some specified class of graphs, H is isomorphic to an induced subgraph of G provided the order of G is large enough compared to the order of H, where the order of a graph is the number of vertices. Examples of two such results are the following. Theorem 1. Let \delta > 0 and C(\delta) be the class of graphs G satisfying \deg_{G}x \geq (\delta+1/4)n and \deg_{\overline G} \geq (\delta+1/4)n for all x in V(G), where n is the order of G. Then there are functions n(\delta), c(\delta) such that for all G in C(\delta) with |V(G)| > n(\delta) and for all H in D with | V(H)| \leq c(\delta) log n, where D is the class of complete bipartite graphs and their complements, H is isomorphic to an induced subgraph of G. Theorem 2. Let c be a real number, and let C be the class of graphs G such that neither G nor its complement contains a complete graph with at least c log n vertices, where n is the order of G. Then there is a function n(c,k) such that for all graphs G in C with at least n(c,k) vertices and for all graphs H of order k, H is isomorphic to an induced subgraph of G.

**Reviewer: ** L.Lesniak-Foster

**Classif.: ** * 05C35 Extremal problems (graph theory)

**Keywords: ** spanned subgroups of graphs

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag