When polynomial GI implies polynomial (edge) colored GI? Crossposted from MO.

(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 &gt; 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?
Q2: a nice example is the graph labeling gadget used to prove that:

Theorem: Planar 3-connected colored GI $\leq_T^L$ planar 3-connected GI

See Thomas Thierauf, Fabian Wagner: The Isomorphism Problem for Planar 3-Connected Graphs Is in Unambiguous Logspace. Theory Comput. Syst. 47(3): 655-673 (2010)

The "labeling gadget" used preserves the 3-connectedness and planarity constraints.