0
$\begingroup$

Don't understand enough group theory, but two papers appear to give partial results about an open problem.

Edge colored graph isomorphism is isomorphism which preserves the edge coloring (the coloring need not be proper).

GI for circulants is polynomial. Edged-colored GI for circulants is GI complete via the simple reduction $G \to G'$.

Make a clique from $V(G)$ and color an edge $e \in E(G')$ with $1$ iff $e \in E(G)$ and $0$ otherwise. To recover $G$ from $G'$ just take the edges colored $1$.

$G \cong H \iff G' \cong H'$ where the isomorphism preserves the edge coloring.

$G'$ is edge colored clique and hence circulant.

This paper claims:

Abstract. We construct a deterministic algorithm that tests whether two circulant graphs are isomorphic. The running time is $ O(n^2 (\log n)^6 )$, where $n$ is the number of vertices of each graph. Our algorithm works for directed, undirected, and edge-colored circulants.

The exact definition of "edge-colored" is not clear to me.

Paper proving circulant GI is polynomial in a footnote on p.1 claims:

By a graph we mean an ordinary graph, a digraph, or even an edge colored graph

The question:

When is edge colored circulant isomorphism polynomial? What is the restriction on edge coloring?

$\endgroup$
  • $\begingroup$ The standard definition of an edge colouring is that no vertex is incident to two edges of the same colour. $\endgroup$ – Emil Jeřábek Jan 18 '15 at 11:52
  • $\begingroup$ Oh, but Odena defines his terminology clearly: his edge-coloured circulants are not subject to the restriction above, but instead the whole edge-coloured graph structure is supposed to have an $n$-cycle automorphism as in the definition of a circulant. So, your $G'$ is not an edge-coloured circulant unless $G$ was a circulant in the first place. $\endgroup$ – Emil Jeřábek Jan 18 '15 at 12:05
  • $\begingroup$ @EmilJeřábek In GI edge coloring doesn't necessarily mean PROPER edge coloring. $\endgroup$ – joro Jan 18 '15 at 12:08
  • $\begingroup$ Edge-coloured circulant graphs are edge-coloured graphs admitting a cyclic transitive automorphism group. Colouring here is just a map from a set of colours to the edges. $\endgroup$ – Dima Pasechnik Jan 18 '15 at 16:20
  • $\begingroup$ In your reduction attempt, you lose the needed automorphisms, so it does not work. $\endgroup$ – Dima Pasechnik Jan 18 '15 at 16:22

Your Answer

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

Browse other questions tagged or ask your own question.