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