[Nauty] counting orbit size for colored graph/computing transversal

[Brendan McKay]

Hi Johannes,

I'll assume that you are referring to colourings of vertices that are not necessarily
"proper".

The automorphism group that preserves the colours is computed by nauty and Traces.
Just place the colouring in the arrays lab & ptn and set options.defaultptn=FALSE.
Chapter 6 of the manual describes it.

For (2), this is what the program vcolg does.  Run "vcolg --help" to see the options.
The switch -u says to just count, which is recommended first since the number of
distinct colourings can be vast.  (Or use the estimate (#colours)^n / |Aut(G)|, which
is usually pretty accurate.)

To see the colourings, use -T in place of -u.  Here are the last few of the list of
22913 distinct colourings of the cycle C_12 with colours 0,1,2 (vcolg -m3T):

12 12 2 2 2 2 2 2 2 2 2 2 0 0  0 1 0 11 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11
12 12 2 2 2 2 2 2 2 2 2 2 1 0  0 1 0 11 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11
12 12 2 2 2 2 2 2 2 2 2 2 1 1  0 1 0 11 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11
12 12 2 2 2 2 2 2 2 2 2 2 2 0  0 1 0 11 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11
12 12 2 2 2 2 2 2 2 2 2 2 2 1  0 1 0 11 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11
12 12 2 2 2 2 2 2 2 2 2 2 2 2  0 1 0 11 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11


First the number of vertices and the number of edges.  Then the colours, one per
vertex, then the edges of the graph.

There is no program-callable version of vcolg, though a custom output function
can be compiled into it.

To make a canonical labelling of a vertex-coloured graph, define the colouring
as above, also set options.getcanon=TRUE and go.  However, to uniquely
represent the isomorphism class of a coloured graph you need to keep the
sizes of the colour classes as a list in the order you put them into lab&ptn
in addition to the canonically labelled graph.

Brendan.

On 27/1/19 8:31 am, J.K.R. Bausch wrote:
Dear all,

I have the following question, and I'm curious whether nauty/traces can do this.
I'm given a graph G with a large automorphism group Aut(G).

1. Given a coloring c for this graph, compute the _size_ of its orbit under Aut(G).
2. Given a number of colors, compute all possible colorings of G, modulo Aut(G).

Context:
1. I can obviously compute all elements of the orbit myself, but that would be expensive.
What I want is to essentially compute |Aut(G)| / |StabilizerGroup(Aut(G), c)|, which should be much faster and consume less memory.
I know how to do this in e.g. Gap, or Mathematica, but it would be faster for my purposes if I could compute it without leaving C++ - so is this possible with nauty/traces?

2. To specify what exactly I mean: I want _one_ representative per disjoint orbit of all possible colorings of G.
Again there exists an algorithm for doing this for any permutation group, see e.g.
https://arxiv.org/abs/1211.6261
Can nauty/traces generate such a list of colorings directly?

Last but not least, I would be keen to know how performant it is to compute the canonical image for a _lot_ of colorings of a particular graph G.
Currently I simply iterate over said list and call nauty individually.
Does nauty somehow cache its calculation of the automorphism group? Or is there a specific way to call it for this purpose?

Thank you so much for your help!
Best,
Johannes

PS: I asked a variant of this question on stackexchange, where I was pointed to this list:
://mathoverflow.net/questions/321739/nauty-traces-orbit-sizes-for-colored-graph
_______________________________________________
Nauty mailing list
Nauty at anu.edu.au<mailto:Nauty at anu.edu.au>
http://mailman.anu.edu.au/mailman/listinfo/nauty