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?