##
**Zentralblatt MATH**

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

**Zbl.No: ** 375.05034

**Autor: ** Bollobás, Béla; Erdös, Paul; Simonovits, M.; Szemeredi, E.

**Title: ** Extremal graphs without large forbidden subgraphs. (In English)

**Source: ** Ann. Discrete Math. 3, 29-41 (1978).

**Review: ** The theory of extremal graphs without a fixed set of forbidden subgraphs is well developed. However, rather little is known about extremal graphs without forbidden subgraphs whose orders tend to oo with the order of the graph. In this note we deal with three problems of this latter type. Let L be a fixed bipartite graph and let L+E^{n} be the join of L with the empty graph of order m. As our first problem we investigate the maximum of the size e(G^{n}) of a graph G^{n} (i.e. graph of order n) provided G^{n}\not\supset L+E^{[cn]}, where c > 0 is a constant. In our second problem we study the maximum of e(G^{n}) if g^{n}\not\supset K_{2}(r,cn) and G^{n}\not\supset k^{3}. The third problem is of a slightly different nature. Let C^{k}(t) be obtained from a cycle C^{k} by multiplying each vertex by t. We shall prove that if c > 0 then there exists a constant l(c) such that if G^{n}\not\supset C^{k}(t) for k = 3,5,...,21(c)+1, then one can omit [cn^{2}] edges from G^{n} so that the obtained graph is bipartite, provided n > n_{0}(c,t).

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

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag