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?