[Nauty-list] commuting isomorphisms

[Mathieu Dutour]

Dear nauty world,

the nauty program computes automorphism group and isomorphisms between   
graphs. Vertex colored graphs are allowed and recently there was an
extension to consider sparse graphs.

Of course we need to consider other structures like vertex colored graphs
and there are tricks here and there to reduce a problem to a vertex
colored graph. However recently I ran out of my bag of tricks:

If G1 and G2 are edge colored graphs and f1 and f2 are two automorphisms
of G1 and G2, the question is does there exist a graph isomorphism
phi:G1--->G2 such that phi(f1(x)) = f2(phi(x)).

For the question of automorphism, I know how to compute the group of
graph automorphism phi:G-->G such that phi(f(x)) = f(phi(x)). The method
is simply to compute the automorphism group of the graph and to use a
computer algebra system (like GAP or Magma) to compute the commutant.

But as far as I know those techniques do not apply to the isomorphism
problem. Obviously such isomorphisms can be found by backtracking.
But would it be possible to modify nauty so as to take care of this
isomorphism. Nauty has been extended from graphs to sparse graphs
(an extension I do not use) but I wonder why some further extensions
have not been done.  

Ideally, one would take a function pointer and put as input but
apparently this has not been done and I wonder if there are some
fundamental obstacle.

Best,

  Mathieu