# When polynomial GI implies polynomial (edge) colored GI?

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

• How is A052565 relevant here? What are these numbers counting? – Dima Pasechnik Aug 6 '14 at 13:28
• @DimaPasechnik The numbers are the orders of the automorphism groups of subdivision of K_n and they showed up in OEIS (modulo errors). – joro Aug 6 '14 at 13:38
• Do you mean a particular subdivision of $K_n$? (I have trouble reading English with missing articles). In your description, you seem to have defined a family of subdivisions for a given $n$, not just one particular. – Dima Pasechnik Aug 6 '14 at 14:24
• @DimaPasechnik I believe this is the usual meaning of subdivision: by subdivision I mean subdivide every edge once: (u,v) becomes (u,(u,v))((u,v),v). – joro Aug 6 '14 at 14:30
• OK; then please write "the subdivision", not just "subdivision". Anyhow, I am sure that the automorphism group of such a graph is easy to describe for any $n$. (not sure though what you mean by "tractable to compute" - by some particular algorithm? Or do you mean "describe"?) – Dima Pasechnik Aug 6 '14 at 14:35