On a Problem of Judicious k ‐Partitions of Graphs

For positive integers k ≥ 2 and m , letg k ( m )be the smallest integer such that for each graph G with m edges there exists a k ‐partition V ( G ) = V 1 ∪ … ∪ V kin which each V i contains at mostg k ( m )edges. Bollobás and Scott showed thatg k ( m ) ≤ m k 2 + k − 1 2 k 22 m + 1 / 4 − 1 / 2 . Ma and Yu posed the following problem: is it true that the limsup ofm k 2 + k − 1 2 k 22 m − g k ( m )tends to infinity as m tends to infinity? They showed it holds when k is even, establishing a conjecture of Bollobás and Scott. In this article, we solve the problem completely. We also present a result by showing that every graph with a large k ‐cut has a k ‐partition in which each vertex class contains relatively few edges, which partly improves a result given by Bollobás and Scott.