Extremal graphs without large forbidden subgraphs

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 ∞ 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 + Em 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. a graph of order n) provided Gn⊅L + E[cn, where c \u3e 0 is a constant. In our second problem we study the maximum of e(Gn) if Gn⊅K2(r,cn) and Gn⊅ 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 \u3e 0 then there exists a constant l(c) such that if Gn⊅Ck(t) for k = 3, 5, 2l(c) + 1, then one can omit [cn2] edges from Gnso that the obtained graph is bipartite, provided n \u3e n0(c, t). © 1978 North-Holland Publishing Compan