A note on the asymptotic and computational complexity of graph distinguishability (Q1385847)

A graph \(G\) is \(d\)-distinguishable if it has a vertex coloring with \(d\) colors such that \(G\) has no color preserving automorphisms. (Adjacent vertices may receive the same color. Indeed, the only purpose of the graph in this theory seems to be to specify a group of vertex permutations.) The cycle norm of \(G\), \(c(G)\), is \(| V| - k\), where \(k\) is the greatest number of disjoint cycles in a non-trivial element of \(\Aut(G)\), regarded as a vertex permutation. Clearly, the more disjoint cycles that a vertex permutation has, the more symmetric colorings it will have. The authors use this observation to conclude that \[ c(G)\ln(d) > \ln(| \Aut(G)|)\text{ implies that \(G\) is \(d\)-distinguishable}. \] The second half of the paper examines the computational complexity of determining the \(d\)-distinguishability of a graph \(G\). Whether or not it is NP-hard is an open problem. The authors present compelling evidence that it is not coNP-hard. For a basic reference on this subject see \textit{M. O. Alberson} and \textit{K. L. Collins} [Electron. J. Comb. 3, No. 1, Paper R18 (1996; Zbl 0851.05088)].