Bounds for pairs in judicious partitioning of graphs1. Issue 1 (26th February 2016) - Fan, Genghua; Hou, Jianfeng
Abstract: In 2002, Bollobás and Scott posed the following problem: for an integer k ≥ 2 and a graph G of m edges, what is the smallest f ( k, m ) such that V ( G ) can be partitioned into V 1, …, V k in which e ( V i ∪ V j ) ≤ f ( k, m ) for all 1 ≤ i ≠ j ≤ k, where e ( V i ∪ V j ) denotes the number of edges with both ends in V i ∪ V j ? In this paper, we solve this problem asymptotically by showing that f ( k, m ) ≤ m / ( k − 1 ) + o ( m ) . We also show that V ( G ) can be partitioned into V 1, …, V k such that e ( V i ∪ V j ) ≤ 4 m / k 2 + 4 Δ / k + o ( m ) for 1 ≤ i ≠ j ≤ k, where Δ denotes the maximum degree of G . This confirms a conjecture of Bollobás and Scott. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 59–70, 2017