On judicious partitions of graphs

Let $$k, m$$ k , m be positive integers, let $$G$$ G be a graph with $$m$$ m edges, and let $$h(m)=\sqrt{2m+\frac{1}{4}}-\frac{1}{2}$$ h ( m ) = 2 m + 1 4 - 1 2 . Bollobás and Scott asked whether $$G$$ G admits a $$k$$ k -partition $$V_{1}, V_{2}, \ldots , V_{k}$$ V 1 , V 2 , … , V k such that $$\max _{1\le i\le k} \{e(V_{i})\}\le \frac{m}{k^2}+\frac{k-1}{2k^2}h(m)$$ max 1 ≤ i ≤ k { e ( V i ) } ≤ m k 2 + k - 1 2 k 2 h ( m ) and $$e(V_1, \ldots , V_k)\ge {k-1\over k} m +{k-1\over 2k}h(m) -\frac{(k-2)^{2}}{8k}$$ e ( V 1 , … , V k ) ≥ k - 1 k m + k - 1 2 k h ( m ) - ( k - 2 ) 2 8 k . In this paper, we present a positive answer to this problem on the graphs with large number of edges and small number of vertices with degrees being multiples of $$k$$ k . Particularly, if $$d$$ d is not a multiple of $$k$$ k and $$G$$ G is $$d$$ d -regular with $$m\ge {9\over 128}k^4(k-2)^2$$ m ≥ 9 128 k 4 ( k - 2 ) 2 , then $$G$$ G admits a $$k$$ k -partition as desired. We also improve an earlier result by showing that $$G$$ G admits a partition $$V_{1}, V_{2}, \ldots , V_{k}$$ V 1 , V 2 , … , V k such that $$e(V_{1},V_{2},\ldots ,V_{k})\ge \frac{k-1}{k}m+\frac{k-1}{2k}h(m)-\frac{(k-2)^{2}}{2(k-1)}$$ e ( V 1 , V 2 , … , V k ) ≥ k - 1 k m + k - 1 2 k h ( m ) - ( k - 2 ) 2 2 ( k - 1 ) and $$\max _{1\le i\le k}\{e(V_{i})\}\le \frac{m}{k^{2}}+\frac{k-1}{2k^{2}}h(m)$$ max 1 ≤ i ≤ k { e ( V i ) } ≤ m k 2 + k - 1 2 k 2 h ( m ) .