Balanced judicious bipartitions of graphs

A bipartition of the vertex set of a graph is called balanced if the sizes of the sets in the bipartition differ by at most one. B. Bollobás and A. D. Scott, Random Struct Alg 21 (2002), 414–430 conjectured that if G is a graph with minimum degree of at least 2 then V ( G ) admits a balanced bipartition V 1 , V 2 such that for each i , G has at most | E ( G )|/3 edges with both ends in V i . The minimum degree condition is necessary, and a result of B. Bollobás and A. D. Scott, J. Graph Theory 46 (2004), 131–143 shows that this conjecture holds for regular graphs G (i.e., when Δ( G )=δ( G )). We prove this conjecture for graphs G with \documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}\begin{eqnarray*}\Delta(G)\le\frac{7}{5}\delta(G)\end{eqnarray*}\end{document} ; hence, it holds for graphs ]ensuremathG with \documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}\begin{eqnarray*}\delta(G)\ge\frac{5}{7}|V(G)|\end{eqnarray*}\end{document} . © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 210–225, 2010