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?

Improve this question
$\endgroup$
7
  • $\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
    Commented Jan 18, 2015 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
    Commented Jan 18, 2015 at 12:05
  • $\begingroup$ @EmilJeřábek In GI edge coloring doesn't necessarily mean PROPER edge coloring. $\endgroup$
    – joro
    Commented Jan 18, 2015 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
    Commented Jan 18, 2015 at 16:20
  • $\begingroup$ In your reduction attempt, you lose the needed automorphisms, so it does not work. $\endgroup$
    – Dima Pasechnik
    Commented Jan 18, 2015 at 16:22

0

Reset to default

You must log in to answer this question.