Bounds for pairs in partitions of graphs

In this paper we study the following problem of Bollobás and Scott: What is the smallest f(k,m) such that for any integer k≥2 and any graph G with m edges, there is a partition V(G)=⋃i=1kVi such that for 1≤i≠j≤k, e(Vi∪Vj)≤f(k,m)? We show that f(k,m)<1.6m/k+o(m), and f(k,m)<1.5m/k+o(m) for k≥23. (While the graph K1,n shows that f(k,m)≥m/(k−1), which is 1.5m/k when k=3.) We also show that f(4,m)≤m/3+o(m) and f(5,m)≤4m/15+o(m), providing evidence to a conjecture of Bollobás and Scott. For dense graphs, we improve the bound to 4m/k2+o(m), which, for large graphs, answers in the affirmative a related question of Bollobás and Scott.