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(2m2-n3)/[n2(n2-2m)],m-4m2/n2} 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))n2 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 cn2 edges can be made bipartite by the omission of at most m/2-\epsilon n2 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) (½)m1/3-1 \leq f(n,m) \leq cm1/3 log2m if m < n3/2,
(ii) 4m2/n4 \leq f(n,m) \leq c(m3/n4) log2(n2/m) if m \geq n3/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