  This paper deals with the complexity of some natural graph problems when
parametrized by {measures that are restrictions of} clique-width, such as
modular-width and neighborhood diversity. The main contribution of this paper
is to introduce a novel parameter, called iterated type partition, that can be
computed in polynomial time and nicely places between modular-width and
neighborhood diversity. We prove that the Equitable Coloring problem is
W[1]-hard when parametrized by the iterated type partition. This result extends
to modular-width, answering an open question about the possibility to have FPT
algorithms for Equitable Coloring when parametrized by modular-width. Moreover,
we show that the Equitable Coloring problem is instead FTP when parameterized
by neighborhood diversity. Furthermore, we present simple and fast FPT
algorithms parameterized by iterated type partition that provide optimal
solutions for several graph problems; in particular, this paper presents
algorithms for the Dominating Set, the Vertex Coloring and the Vertex Cover
problems. While the above problems are already known to be FPT with respect to
modular-width, the novel algorithms are both simpler and more efficient: For
the Dominating set and Vertex Cover problems, our algorithms output an optimal
set in time $O(2^t+poly(n))$, while for the Vertex Coloring problem, our
algorithm outputs an optimal set in time $O(t^{2.5t+o(t)}\log n+poly(n))$,
where $n$ and $t$ are the size and the iterated type partition of the input
graph, respectively.
