[Nauty] Searching for automorphisms of only one colour

[Christopher Jefferson]

At 00:51 15/10/2002 +1000, Brendan McKay wrote:
>* Christopher Jefferson <caj at cs.york.ac.uk> [021015 00:23]:
> >
> > My "problem" is that I have a coloured graph where the first "colour"
> > represents variables and the other coloured nodes represent various
> > relations. Stabilizing these other groups is quite easy, as the generators
> > for them are separate, so I just cut them out of the answer. While this
> > works quite well, I expect that if there as some way I could search for
> > only the automorphisms of one colour, things would go even faster!
> >
> > Is there a way to do this, or simple alteration I could make to nauty 
> to do
> > this?
>
>Without knowing the graph structure I can't be sure I'm answering
>the right question.  Is this the problem:
>    There may be symmetries amongst the relations even when the
>    variables are all fixed, and you don't want such symmetries
>    to appear in the nauty output. ??
>Is it true by any chance that the relation vertices are only
>joined to variable vertices?  And vice-versa?


Yep, relations are only joined to variables, and variables to relations, so 
actually the graph is bi-pirate (I hadn't noticed before...) with the 
variables in one part and the relations in the other. However it is still 
important that some relations are different colours to one each another.

In fact, I want something stronger, I want only those symmetries that only 
permute variables. I can do this by finding all the symmetries and then 
"stabilizing" all the relations one by one. However, it might be possible 
to do it faster?

Also, one small thing that did not occur to me before, but I expect is OK. 
I tried to find a definition of isomorphism on graphs with coloured 
vertices and could not find one. I am assuming that (trivial case) if I 
have 4 vertices, 1,2,3,4 s.t. 1 is connected to 2, and 3 is connected to 4, 
and they are split into colour groups {1,2} , {3} , {4}, then there is no 
automorphisms? (so I can't do (1,2) ).

Thank you for your time,

Chris


>I'll say more when you reply to the above.  Or at least when
>I wake up (now it is 00:50am here).
>
>Brendan.
>
>_______________________________________________
>This is the nauty mailing list
>Post messages to nauty-list at cs.anu.edu.au
>nauty page: http://cs.anu.edu.au/~bdm/nauty/
>list page: http://cs.anu.edu.au/mailman/listinfo/nauty-list