History

Please fill in your query. A complete syntax description you will find on the General Help page.
Sparse balanced partitions and the complexity of subgraph problems. (English)
SIAM J. Discrete Math. 25, No. 2, 631-644 (2011).
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)