Finding automorphisms of totally colored graphs with nauty/traces The nauty and traces software package is able to calculate automorphism groups of vertex colored graphs. The accompanying manual also describes (in section 14) how to obtain automorphism groups of edge colored graphs by mapping the problem to an equivalent one over vertex colored graphs.
My question is whether there exists a similar approach for the same problem over totally colored graphs. One possible solution might be to compute the automorphism groups for variants of such a graph with vertex-/edge-only coloring first and to then compute their intersection but I believe that this might be computationally expensive and would also require a base and strong generating set for both these groups which are internally generated by nauty but not actually accessible via its C-interface (at least that is my impression after reading the manual).
Can anyone give me a suggestion as to what would be the most efficient approach from a practical standpoint?
 A: The simplest approach that comes to mind without knowing the specifics of how nauty works is to subdivide the graph, putting a vertex in the middle of every edge, and using disjoint color sets on the old and new vertices. This reduces the total-coloring automorphism problem to the vertex-coloring automorphism problem.
A: For vertex colors, it is as simple as partitioning the vertices by color before running the algorithm, I believe.
I have done this for graphs with both vertex and edge colors (not 'colorings' in the strict sense, but more like non-unique labels for the vertices/edges) and it seems to work fine.
However, my approach does not use the 'trick' that the nAUTy/Traces manual describes of encoding edge colors as layers in the graph. Instead, the certificate I build uses the edge colors; so instead of a certificate like 101001100, I have 302001100.
I suspect that there may be implementation reasons why they suggest the multi-layer trick, but starting with a partition of the vertex colors should work either way.
