2005/03/21 by D. Kuehn, Daniela Kuehn, Kuehn, Daniela +2
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Limits and Structures in Graph Theory #math.CO #msc:05C35 #msc:05C85 #msc:05D40
paper · pdf · doi:10.48550/arxiv.math/0503403
arxiv created 2005/03/21 · arxiv updated 2009/12/01
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 the number of edges between A and B in Gi is (1+o(1))mi/2. This answers a question of Bollobas and Scott. We also prove results about partitions into more than two vertex classes.