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?
In general, if the number of adjacent edges, which have the same color, is bounded by a constant, say d. Then, the isomorphism problem for n-vertex graphs can be solved in n^(cd) for some constant c. In your case, d=1. See for example, Proposition 4.5 in CANONICAL LABELING OF GRAPHS by Babai and Luks. Actually, they considered vertex coloring, but the same arguments works for edge colors as well. For example, you could subdivide each edge and instert a new vertex that encodes the edge color.