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 = 1 k V i such that for 1 ≤ i ≠ j ≤ k , e ( V i ∪ V j ) ≤ f ( k , m ) ? We show that f ( k , m ) < 1.6 m / k + o ( m ) , and f ( k , m ) < 1.5 m / k + o ( m ) for k ≥ 23 . (While the graph K 1 , n shows that f ( k , m ) ≥ m / ( k − 1 ) , which is 1.5 m / k when k = 3 .) We also show that f ( 4 , m ) ≤ m / 3 + o ( m ) and f ( 5 , m ) ≤ 4 m / 15 + o ( m ) , providing evidence to a conjecture of Bollobás and Scott. For dense graphs, we improve the bound to 4 m / k 2 + o ( m ) , which, for large graphs, answers in the affirmative a related question of Bollobás and Scott.