Let $G=(V,E)$ be a graph of order $n$ and of maximum degree $d.\, $It is shown in the paper that for $n$ big enough there is a partition of $V$ into $ k$ parts $V_{1},...,V_{k}$ of size at most $\left\lceil \frac{n}{k} \right\rceil $ so that the number of pair $(i,j)$ for which there is an edge between $V_{i}$ and $V_{j}$ is at most $O(k^{2-2/d})$ and there are graph for which $Ω(k^{2-2/d})$ pairs are needed.
Reviewer: Peter Horák (Tacoma)