##
**Zentralblatt MATH**

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

**Zbl.No: ** 729.05025

**Autor: ** Erdös, Paul; Faudree, Ralph J.; Pach, János; Spencer, Joel

**Title: ** How to make a graph bipartite. (In English)

**Source: ** J. Comb. Theory, Ser. B 45, No.1, 86-98 (1988).

**Review: ** The following theorems are proved:

(1) Every triangle-free graph with n vertices and m edges can be made bipartite by the omission of at most **max** **{**(m/2)-2m(2m^{2}-n^{3})/[n^{2}(n^{2}-2m)],m-4m^{2}/n^{2}**}** edges.

(2) There exists a constant \epsilon > 0 such that every triangle-free graph with n vertices can be made bipartite by the omission of at most (1/18-\epsilon+o(1))n^{2} edges.

(3) For every forbidden graph F and for every c > 0 there exists a constant \epsilon = \epsilon (F,c) > 0 such that any F-free graph with n vertices and m \geq cn^{2} edges can be made bipartite by the omission of at most m/2-\epsilon n^{2} edges.

(4) If f = f(n,m) is the maximum integer such that every triangle-free graph with n vertices and at least m edges contains an induced bipartite subgraph with at least f edges then

(i) (½)m^{1/3}-1 \leq f(n,m) \leq cm^{1/3} log^{2}m if m < n^{3/2},

(ii) 4m^{2}/n^{4} \leq f(n,m) \leq c(m^{3}/n^{4}) log^{2}(n^{2}/m) if m \geq n^{3/2}.

Several related questions, generalizations and unsolved problems are also considered.

**Reviewer: ** A.Rosa (Hamilton/Ontario)

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

05C99 Graph theory

**Keywords: ** triangle-free graph; bipartite; forbidden graph

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag