I'm given a graph $G$ (<1000 vertices, large automorphism group), and a large number (~10^6-10^10) of different colorings of said graph. I have two tasks.

  1. Calculate the canonical coloring. I can use nauty, traces, or bliss for this. Question: what's the most optimal way of doing this to avoid re-calculating automorphism groups over and over, e.g. in nauty/traces?
  2. I need to now calculate the size of the orbit for each canonical coloring. Question: I could not figure out whether that's possible in nauty or traces. Is it?

Re. 1: I currently just iterate over the list of colorings and call nauty separately; that seems inefficient, but I'm not familiar with the implementation details to tell whether there's a faster way. I'd be grateful for any pointers.

Re. 2: In principle I can of course calculate the full orbit and count the elements. That's naturally slow. A faster way would be to calculate $ord(G)/ord(\text{stabilizer subgroup of given coloring})$. Can nauty or traces do this, or in an even faster way somehow?

Thanks a lot! - J

  • $\begingroup$ A much better place for this is the nauty/traces mailing list at users.cecs.anu.edu.au/~bdm/nauty. Questions are using software generally get closed here. And I don’t know what a “canonical coloring” is. $\endgroup$ – Chris Godsil Jan 26 at 13:09
  • $\begingroup$ thanks for the comment! I wasn't sure whether this is the right place, but the "nauty" tag links to a series of past questions related to nauty/traces; it appears to be almost a standard tool for graph isomorphism questions, and the author of it, McKay, appears active too. edit: to answer your question: a canonical coloring is when you have a colored graph and you map it to a "canonical" one using the graph's automorphism group. See e.g. math.unl.edu/%7Earadcliffe1/Papers/Canonical.pdf $\endgroup$ – J Bausch Jan 26 at 21:01

Your Answer

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

Browse other questions tagged or ask your own question.