Abstract
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 eG(i) (A, B) >= m(i)/2 - root(m(i)) over bar. This gives an approximate answer to a question of Bollobas and Scott. We also prove results about partitions into more than two vertex classes. Our proofs yield polynomial algorithms.
| Original language | English |
|---|---|
| Pages (from-to) | 277-283 |
| Number of pages | 7 |
| Journal | Combinatorics, Probability and Computing |
| Volume | 16 |
| Issue number | 02 |
| Early online date | 14 Aug 2006 |
| DOIs | |
| Publication status | Published - 1 Mar 2007 |