  We consider the problem of partitioning a graph into a non-fixed number of
non-overlapping subgraphs of maximum density. The density of a partition is the
sum of the densities of the subgraphs, where the density of a subgraph is its
average degree, that is, the ratio of its number of edges and its number of
vertices. This problem, called Dense Graph Partition, is known to be NP-hard on
general graphs and polynomial-time solvable on trees, and polynomial-time
2-approximable. In this paper we study the restriction of Dense Graph Partition
to particular sparse and dense graph classes. In particular, we prove that it
is NP-hard on dense bipartite graphs as well as on cubic graphs. On dense
graphs on $n$ vertices, it is polynomial-time solvable on graphs with minimum
degree $n-3$ and NP-hard on $(n-4)$-regular graphs. We prove that it is
polynomial-time $4/3$-approximable on cubic graphs and admits an efficient
polynomial-time approximation scheme on graphs of minimum degree $n-t$ for any
constant $t\geq 4$.
