A bound for judicious kk-partitions of graphs

Judicious Partition Problem   is to partition the vertex set of a graph such that certain quantities are optimized simultaneously. Let kk be a positive integer and GG a graph with mm edges. It is proved in this paper that the vertex set of GG can be partitioned into kk parts V1,…,VkV1,…,Vk such that e(Vi)≤mk2+k−12k2(2m+14−12)+23 for each i∈{1,2,…,k}i∈{1,2,…,k} and e(V1,…,Vk)≥k−1km+k−12k(2m+14−12)−(k−2)28k, where e(Vi)e(Vi) is the number of edges with both ends in ViVi and e(V1,…,Vk)=m−∑i=1ke(Vi). This partially solves a problem proposed by Bollobás and Scott, and, for some values of mm, solves the problem affirmatively.