# Complexity of graph isomorphism with properly colored edges (ref. request)

An edge-colored graph $$G$$ is a graph whose edges are labeled with a color (generally represented by an integer). Such a coloring is proper if all adjacent edges in $$G$$ have different colors. I recently realized that isomorphism between two such graphs can be tested in polynomial time. The arguments are pretty simple and the question natural, so this fact should already be mentioned somewhere. However, I could not find it so far.

The arguments: Fix an arbitrary vertex $$v_1$$ in $$G_1$$. We will try to send it to every vertex $$v_2$$ of $$G_2$$ successively, until either a valid bijection is found (accept) or all the vertices of $$G_2$$ have been tried (reject). The key point is that once the selection of $$v_2$$ is made, no other choice remains to be done, because local constraints imposed by the colors recursively determine the remaining of the bijection. For instance, if $$v_1$$ shares an edge colored $$c$$ with vertex $$u_1$$, then this vertex must be sent to a vertex that shares an edge colored $$c$$ with $$v_2$$. This vertex (if any qualifies) must be unique due to the fact that the coloring is proper.

Has anyone seen such an observation somewhere or has an idea where to find it?

• This argument is very close to the one showing that the exact version of unique label cover is solvable in polynomial time. Dec 19, 2019 at 5:08
• Suggest you edit the post to clarify that by "isomorphism between two such graphs" you mean one that preserves the edge colors (which is not the standard definition of an isomorphism between graphs). Dec 29, 2019 at 14:35

• Definitely, this reduction implies a polynomial time algorithm, which is worth knowing, thanks! Now, looking at Proposition 4.5 (and 4.2, which it extends), the arguments are group-theoretic. If I understand well, having at most $d$ neighbors of the same color essentially implies that the factors of the composition series of $Aut(G)$ are subgroups of $S_d$, which is enough to know. In contrast, the arguments in my question are almost direct (and the setting natural), so I'll keep the question open a bit longer to see if anyone has seen these particular arguments (and eventually accept if not). Dec 24, 2019 at 16:30