(edge) colored graph isomorphism is GI which preserves the colors (of edges if it is edge colored).

There are several reductions using transformations/gadgets of (edge) colored GI to GI. For edge colored GI the simplest is to replace colored edge by a GI preserving gadget encoding the color (subdividing edge enough times is the simplest case). For vertex colored GI, attach some gadget to a vertex.

Suppose GI is polynomial for some graph class $C$.

Q1 For which $C$ polynomial GI implies polynomial (edge) colored GI?

Using a reduction with gadgets might make the graphs not members of $C$.

On the other hand certain gadgets/transformations might make the graphs members of some other polynomial GI class.

Example of edge colored reduction $ G \to G'$.

Make a clique of $V(G)$. Color edges in $E(G)$ with $1$ and non-edges with $0$. It is the coloring function that preserves $G$ and to recover $G$ from $G'$ just take the edges colored $1$. $G'$ is clique, cograph, permutation graph and almost sure in many other nice classes. Subdividing the edges odd number of times (distinct for $0,1$ removes the colors and makes $G'$ perfect bipartite graph, preserving isomorphism).

Maybe another approach is to take the line graph of $G'$ and add pendant (universal) vertices connected to vertices corresponding to $E(G')$.

Q2 Are there nice gadgets/transformations for similar constructions?

Thought about planarizing $G'$ by choosing some universal drawing of the clique and replacing edge crossing by planar gadgets preserving colors say $C_4,C_6$ for equal colors and something else for distinct colors. Don't know if this preserves isomorphism.

Another possible approach might be automorphism preserving coloring or subdivide every edge of $K_n$, use 3 colors ${0,1,2}$ for vertices $V(G),E(G),E(\overline{G})$ and try to recognize self complementary graphs by automorphism exchanging $E(G)$ and $E(\overline{G})$.

Q3 Is the automorphism group of the subdivision of $K_n$ tractable to compute?

The orders after the few initial terms are $12 , 24 , 120 , 720 , 5040 , 40320 , 362880$ which is A052565

Dima suggests this might be easy for $n$ large enough and the initial terms are exceptions.

Q4 Given vertex colored subdivision of $K_n$ for $n > 4$ and its automorphism group where the high degree vertices are colored $0$, some degree $2$ are $1$ and the other are $2$, what is the complexity to find automorphism exchanging $1$ and $2$?

**Added** The paper On Recognizing Cayley Graphs p 86 claims:

Given a class C of Cayley graphs, and given an edge-colored graph G of n vertices and m edges, we are interested in the problem of checking whether there exists an isomorphism φ preserving the colors such that G is isomorphic by φ to a graph in C colored by the elements of its generating set. In this paper, we give an O(m log n)-time algorithm to check whether G is color-isomorphic to a Cayley graph.

This appears close to the question, is it relevant?