Minimal Partitions of a Graph

Abstract

For a given graph $G$, we fix $s$, and partition the vertex set into $s$ classes, so that any given class contains few edges. The result gives a partition $(U_1,U_2,\dots ,U_s)$, where $e(U_i)\le \frac{e(G)}{s^2}+4s\sqrt{e(G)}$ for each $1\le i\le s$. The error term is compared to previous results for $s=2^P$ $[6]$, and to a result by Bollobás and Scott $[1]$.