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?

  • $\begingroup$ This argument is very close to the one showing that the exact version of unique label cover is solvable in polynomial time. $\endgroup$ – Yonatan N Dec 19 '19 at 5:08
  • $\begingroup$ 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). $\endgroup$ – Neal Young Dec 29 '19 at 14:35

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.

  • $\begingroup$ 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). $\endgroup$ – Arnaud Casteigts Dec 24 '19 at 16:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.