New answers tagged graph-colouring
0
Your problem is equivalent to Graph Isomorphism under polynomial-time reductions, even if you include edge colors.
First, GI is equivalent (under polynomial-time Turing reductions) to computing generators of the automorphism group. From those generators it is easy (using standard permutation group machinery) to compute the edge orbits in polynomial time.
...
3
It turns out that yes, indeed, there are two possible definitions for edge-automorphisms... but it turns out that they almost always coincide so that it seems that people often get away with not making the distinction.
First, some notation. For a simple graph $G = (V,E)$ we let $\Gamma_V(G)$ define the group of automorpisms over the set of vertices $V$ ...
6
This problem is equivalent to feedback arc set (in a tournament graph). It is NP-hard.
Top 50 recent answers are included
