Judicious k-partitions of graphs

Judicious partition problems ask for partitions of the vertex set of graphs so that several quantities are optimized simultaneously. In this paper, we answer the following judicious partition question of Bollobás and Scott [B. Bollobás, A.D. Scott, Problems and results on judicious partitions, Random Structures Algorithms 21 (2002) 414–430] in the affirmative: For any positive integer k and for any graph G of size m  , does there exist a partition of V(G)V(G) into V1,…,VkV1,…,Vk such that the total number of edges joining different ViVi is at least k−1km, and for each i∈{1,2,…,k}i∈{1,2,…,k} the total number of edges with both ends in ViVi is at mostmk2+k−12k2(2m+14−12)? We also point out a connection between our result and another judicious partition problem of Bollobás and Scott [B. Bollobás, A.D. Scott, Problems and results on judicious partitions, Random Structures Algorithms 21 (2002) 414–430].