When polynomial GI implies polynomial (edge) colored GI?

Question

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 > 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?

Answer 1

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.

Answer 2

Partial answer, don't understand enough group theory, but two papers appear to give partial results.

GI for circulants is polynomial. Edged-colored GI for circulants is GI complete via the simple reduction $G \to G'$.

Make a clique from $V(G)$ and color an edge $e \in E(G')$ with $1$ iff $e \in E(G)$ and $0$ otherwise. To recover $G$ from $G'$ just take the edges colored $1$.

$G \cong H \iff G' \cong H'$ where the isomorphism preserves the edge coloring.

$G'$ is edge colored clique and hence circulant.

This paper claims:

Abstract. We construct a deterministic algorithm that tests whether two circulant graphs are isomorphic. The running time is $ O(n^2 (\log n)^6 )$, where $n$ is the number of vertices of each graph. Our algorithm works for directed, undirected, and edge-colored circulants.

The exact definition of "edge-colored" is not clear to me.

Paper proving circulant GI is polynomial in a footnote on p.1 claims:

By a graph we mean an ordinary graph, a digraph, or even an edge colored graph

Asked on MO what are the restrictions for the colorings.