##
**Zentralblatt MATH**

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

**Zbl.No: ** 785.05052

**Autor: ** Erdös, Paul; Györi, E.; Simonovits, M.

**Title: ** How many edges should be deleted to make a triangle-free graph bipartite? (In English)

**Source: ** Halász, G. (ed.) et al., Sets, graphs and numbers. A birthday salute to Vera T. Sós and András Hajnal. Amsterdam: North-Holland Publishing Company, Colloq. Math. Soc. János Bolyai. 60, 239-263 (1992).

**Review: ** We shall prove that if L is an arbitrary 3-chromatic graph and G_{n} is a simple graph on n vertices not containing L, and having at least {n^{2}\over 5}-o(n^{2}) edges, then it can be made bipartite by throwing away at most {n^{2}\over 25}-o(n^{2}) edges. This was known for L = K_{3}.

Let us call a graph pentagonlike if we can colour its 5 classes so that the vertices coloured by i are joined only to vertices coloured by i± 1\pmod 5.

In addition to the above assertions, we shall prove that under the above conditions, there is a ``pentagonlike graph'' H_{n} with e(H_{n}) = e(G_{n}) for which we have to delete more edges than in case of G_{n} to make it bipartite. We shall also prove a related stability theorem, according to which, if D(G_{n}) denotes the minimum number of edges to be deleted to make G_{n} bipartite, then either D(G_{n}) \leq D(H_{n})-cn^{2}; i.e. G_{n} is significantly better than H_{n}–though they both may be far from any bipartite graph–or the structure of G_{n} is very near to that of a pentagonlike graph.

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

05C15 Chromatic theory of graphs and maps

**Keywords: ** stability theorem

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag