[Nauty] Orbits partition refinement

[Brendan McKay]

Hello Dmitrii, Welcome to the list.

> Suppose:
> 
> 1. G is a colored simple graph;
> 2. G has N vertex orbits under Aut(G);
> 3. Vertices in the ith orbit have same color = i (i=1,...,N);
> 4. Vertex v of G belongs to an orbit that has more than one vertex;
> 5. Graph G' is made out of G by changing color of v to a new color = N+1.
> 6. A refinement procedure applied to G' produced coarsest equitable partition P'.
> 
> Questions:
> 
> 7. Is P' the orbits partition of G' under Aut(G')?

Not necessarily.
 
> 8. If yes, then how to prove it? If not or sometimes, how to build the smallest/simplest counterexample?

Good question.  I know there are examples where the whole group Aut(G)
is transitive, but the refinement wrt one vertex is coarser than the
orbits of the stabiliser.  Maybe Gordon has one in his head already;
I'll have to think about it.
 
> If I understand correctly, 5-6 closely resembles what nauty would do to G under certain circumstances.

Right.  If refinement always gave orbits then nauty would run in 
polynomial time, but life is not so kind.

Brendan.