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?


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.

  • $\begingroup$ I think I might understand what you mean but I'm having trouble with the terminology. What do you mean by "partitioning the vertices by color"? A given vertex coloring is a partition of the vertices and also seemingly the only input parameter for a call to nauty despite the graph structure itself. $\endgroup$ – Peter Jul 9 '18 at 13:28
  • $\begingroup$ Right, so that's what I mean - the basic algorithm already works on an initial partition of the vertices, and coloring the vertices is just one possible initial partition (another could be a partition by degree). So for both vertex and edge colors, the multi-layer structure described in the manual just needs the color partition as input. $\endgroup$ – gilleain Jul 9 '18 at 13:34
  • $\begingroup$ Okay that makes sense. In the structure described (for the edge coloring case) each vertex every layer is colored with the same color unique to that layer, so what you are suggesting is additionally partitioning each layer according to the original vertex coloring for the totally colored case, right? (such that $|Vertexcolors| \cdot log_2(|Edgecolors|)$ unique vertex colors would be used here). I will quickly try to implement this. $\endgroup$ – Peter Jul 9 '18 at 13:46
  • $\begingroup$ I have the same question. Did this work in the end Peter? $\endgroup$ – SLesslyTall Sep 3 '18 at 19:46

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.

  • $\begingroup$ I will try this out as well, I could imagine that gilleains version will be faster in most cases because the computation can be carried out over a smaller number of vertices. $\endgroup$ – Peter Jul 9 '18 at 14:56
  • $\begingroup$ But what about two edges being incident at the same vertex? Just putting a vertex at the middle of each edge would not capture that, right? $\endgroup$ – vidyarthi Jan 10 at 11:10
  • $\begingroup$ I was assuming simple graphs, but we can (1) in the case of parallel edges of different colors, proceed as usual; (2) in the case of $k$ parallel edges of the same color, subdivide that edge $k$ times instead. $\endgroup$ – Misha Lavrov Jan 10 at 13:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.