Colored graph isomorphisms: 1(red)->2(blue) vs 1(blue)->2(red)

Question

Given two simple graphs:

library(igraph)

g <- graph.empty()
g <- g + vertices(1,2,3)
g <- g + path(1,2,3)


g1 <- g
V(g1)$color = c(1,2,2)
g2 <- g
V(g2)$color = c(2,1,1)

which look like:

par(mfrow=c(1,2))
palette(rainbow(3))
plot(g1)
plot(g2)

How come they are not isomorphic?

graph.isomorphic.vf2(g1,g2)$iso

FALSE

and most important, if this is not an isomorphism, how can I detect this kind of equivalence within igraph ?

Answer 1

To avoid color permutations, Bertrand Jouve pointed to me to this trick suggested in the nauty user guide (pages 58-59). The idea is to recolour the vertices to be all the same and then all vertices that used to share the same color now have an edge to a common vertex. And then we can apply a classic vf2for colored graphs.

My implementation:

library(igraph)
isocolor.setup <- function(g){
   # Transform a graph so that it can be used in colored isomorphism algorithms
   # Args:
   #   g: graph
   # Returns:
   #   Transformed graph
  nvertices <- vcount(g)
  colors <- unique(V(g)$color)
  g <- add.vertices(g, length(colors), color=max(colors)+1)
  for(i in 1:length(colors)){
    group <- V(g)[V(g)$color==colors[i]]
    aux.id <- nvertices + i
    g[from = group, to = rep(aux.id,length(group))] <- TRUE
  }
  V(g)[1:nvertices]$color <- 1
  V(g)[V(g)$color != 1]$color <- 2
  return(g)
}

Examples:

setup_palette <- function(g){
  palette(rainbow(max(2,length(unique(V(g)$color)))))
}

par(mfrow=c(3,2))

# First graph
g1 <- graph.ring(6)
V(g1)$color <- c(1,1,2,2,3,3)
setup_palette(g1)
plot(g1)

g1.mapped <- isocolor.setup(g1)
setup_palette(g1.mapped)
setup_palette(g1.mapped)
plot(g1.mapped)

# Second graph
g2 <- graph.ring(6)
V(g2)$color <- c(2,3,2,3,1,1)
setup_palette(g2)
plot(g2)

g2.mapped<- isocolor.setup(g2)
setup_palette(g2.mapped)
plot(g2.mapped)
title(paste("\ng1 iso g2?", graph.isomorphic.vf2(g1.mapped, g2.mapped)$iso))

# Third graph
g3 <- graph.ring(6)
V(g3)$color <- c(1,1,3,3,2,2)
setup_palette(g3)
plot(g3)

g3.mapped<- isocolor.setup(g3)
setup_palette(g3.mapped)
plot(g3.mapped)
title(paste("\ng1 iso g3?", graph.isomorphic.vf2(g1.mapped, g3.mapped)$iso))

Of course we should check, as a first filter, whether they both have the same color frequency as explained by @josilber.