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+En be the join of L with the empty graph of order m. As our first problem we investigate the maximum of the size e(Gn) of a graph Gn (i.e. graph of order n) provided Gn\not\supset L+E[cn], where c > 0 is a constant. In our second problem we study the maximum of e(Gn) if gn\not\supset K2(r,cn) and Gn\not\supset k3. The third problem is of a slightly different nature. Let Ck(t) be obtained from a cycle Ck by multiplying each vertex by t. We shall prove that if c > 0 then there exists a constant l(c) such that if Gn\not\supset Ck(t) for k = 3,5,...,21(c)+1, then one can omit [cn2] edges from Gn so that the obtained graph is bipartite, provided n > n0(c,t).
Classif.: * 05C35 Extremal problems (graph theory)
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag