We are talking about undirected simple graphs and *partitions* of their vertex sets into disjoint non-empty *cells*. Such a partition is *equitable* if for any two vertices $v,w$ in the same cell, and any cell $C$, it holds that $v,w$ have the same number of neighbours in $C$. The *trivial* partition (with only one vertex per cell) is always equitable.

Given any partition $\pi$, there is a unique coarsest equitable partition $\bar\pi$ finer than $\pi$. (The concepts *finer* and *coarser* include equality). This is a very old result, as also are polynomial-time algorithms for computing $\bar\pi$ from $\pi$.

Another fact is that it is NP-complete to determine if a graph has an equitable partition with every cell of size 2. (This follows from Lubiw, SIAM J Comput 10, 1981, 11–21 on noting that such a partition corresponds to a fixed-point-free automorphism of order 2.)

My question is: **what else?** Are any other complexity results known? In particular:

- What is the complexity of: Given a regular graph, does it have any non-trivial equitable partition other than the partition with just one cell?
- What is the complexity of: Given a regular graph, does it have an equitable partition with exactly two cells?
- What is the complexity of: Given a graph and two vertices $v,w$, is there a non-trivial equitable partition which has $v,w$ in different cells?
- Is there any problem on equitable partitions with complexity equal to graph isomorphism?

3more comments