Let $G$ be a graph -- possibly infinite, but I will be glad to learn a positive result even in the finite case. Then the trivial partition (i.e., one cell coinciding with the whole $G$) is clearly almost equitable (a definition can be found here, for example), but this is of course very coarse. Another trivial almost equitable partition is instead much too fine: it is the partition consisting of singletons only - this is indeed even equitable.

My question: Is there any way of algorithmically constructing further (non trivial) almost equitable partitions -- that is, almost equitable partitions with a larger number of smaller cells, but not too small? Or almost equitable partitions with a smaller number of larger cells, but not too large?

EDIT: As Aaron Meyerowitz suggests in the comments, the mathoverflow entry linked above does in fact call *almost equitable* what is usually called equitable. So, let me for reference write down here what is the correct definition, even in the general case of a weighted graph: Let $G$ be a (possibly infinite) graph with node set $V$, where each edge $e=(v,w)$ has a weight $\mu_{vw}\in (0,\infty)$ and each node $v$ has a weight $\nu_v\in (0,\infty)$. Given a subset $W\subset V$ and a $v\in V$, one denotes by $d_W(v)$ the *weighted degree* of $v$ in $W$, i.e.,
$$
d_W(v):=\frac{1}{\nu_v} \sum_{w\in V \hbox{ s.t. }w\sim v} \mu_{vw}.
$$
Then, a (possibly infinite) partition $(V_i)_{i\in I}$ of $V$ is called *almost equitable* if for all $i,j\in I$, $i\neq j$, there is a number $c_{ij}$ such that $d_{V_j}(v)=c_{ij}$ for all $v\in V_i$.

yet notone equ-part. If the answer is 'yes' create the tag, if 'no' then rather not. Or... – quid Feb 19 '13 at 19:40