2007/03/01 by DANIELA KÜUHN, DERYK OSTHUS
paper · doi:10.1017/s0963548306007863
Consider two graphs G 1 and G 2 on the same vertex set V and suppose that G i has m i edges. Then there is a bipartition of V into two classes A and B so that, for both i = 1, 2, we have eGi(A,B) ≥ mi/2-√(mi) . 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.