## 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 Gn is a simple graph on n vertices not containing L, and having at least {n2\over 5}-o(n2) edges, then it can be made bipartite by throwing away at most {n2\over 25}-o(n2) edges. This was known for L = K3.
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'' Hn with e(Hn) = e(Gn) for which we have to delete more edges than in case of Gn to make it bipartite. We shall also prove a related stability theorem, according to which, if D(Gn) denotes the minimum number of edges to be deleted to make Gn bipartite, then either D(Gn) \leq D(Hn)-cn2; i.e. Gn is significantly better than Hn–though they both may be far from any bipartite graph–or the structure of Gn 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