Maximizing Several Cuts Simultaneously
DANIELA KÜUHN, Deryk Osthus · Combinatorics Probability Computing · 2006
Consider two graphs G1 and G2 on the same vertex set V and suppose that Gi has mi edges. Then there is a bipartition of V into two classes A and B so that, for both i = 1, 2, we have $e_{G_i}(A,B) \geq m_i/2-\sqrt{m_i}$ . This gives an approximate answer to a question of Bollobás and Scott. We also prove results about partitions into more than two vertex classes. Our proofs yield polynomial algorithms.