counterexample for this graph isomorphism algorithm

Question

I'm trying to learn about graph isomorphism and I stumbled upon coloring. When given 2 graphs, you give each vertex a color according to properties of their neighbors and any vertex on graph 1 can only map to any vertex on graph 2 with the same color. This way you cannot have false negatives (if the algorithm says there's no mapping, it is so) but you may have false positives. So now I'm looking for a false positive of my particular graph isomorphism coloring algorithm.

We're going to assign each vertex a "breadth" and a "color", which are both strings. Assume both graphs have n vertices.

Step 1: we assign depth=0. We pick a starting vertex and assign it
(breadth, color) = ("0;","0;").
We assign a set S={that vertex}.

    Step 2: depth++;
    set T=[all neighbors that don't have a color yet of all vertices in S].

        Step 2.A: for each vertex in T, name it t and set t.breadth = depth + ";"

        Step 2.B: for each t in T:
        t.breadth += '[' + (concatenate all colors of all
        neighbours of t that are in S, in lexicographically sorted order) + '];'

        Step 2.C: for each t in T:
        t.color = t.breadth + '{'+(all breadths of all neighbours
        of t that are in T, concatenated in lexicographically sorted order)+'}'

    Step 2.D: S=T; goto step 2 unless T is empty.

Step 3: Save the resulting coloring, clear S and T and the coloring and 
repeat from step 1 for *each possible starting vertex for both graphs*.

Step 4: We now have n colorings for both graphs. Deduce if this leads to a
negative. If not, for now assume that the graphs are isomorphic.

A bit of explanation on step 4: Suppose I pick a starting vertex for graph 1, we need to look at each starting vertex for graph 2. If a starting vertex for graph 2 then leads the exact same number of colors for each color of graph 1, we have possible vertex mappings from graph 1 to graph 2. If this is also the case for another starting vertex of graph 2, we have extra mapping possibilities. with 1 starting vertex for graph 1, we look at all starting vertices from graph 2 and union the results together.

When looking at another starting vertex for graph 1, we get another set of mappings. Each starting vertex of graph 1 leads to a set of mappings, and we're looking at the interesection of those sets. If that intersection is empty, the graphs are not isomorphic.

Now, I'm looking for two graphs for which this algorithm says they're isomorphic, while they're not.

I'm assuming that the graphs are connected.

Note that the colors might grow exponentially large this way, but we can avoid that by replacing parts with placeholders.

Answer 1

I've not looked closely at your algorithm so I'm not sure exactly what it does. However, it sounds quite a lot like colour refinement (also known as the 1-dimensional Weisfeiler-Lehman method). I suggest you look at the following paper, which will both explain that method and show a class of graphs whose isomorphism problem it cannot solve, even though graph isomorphism on those specific graphs is in P. Even if your algorithm turns out to be different from colour refinement, a similar construction might give some graphs it doesn't work on.

• J.-Y. Cai, M. Fürer and N. Immerman, An Optimal Lower Bound on the Number of Variables for Graph Identification. Combinatorica, 12(4):389–410, 1992. (Free PDF)

By the way, one thing you can (probably) do to avoid the labels your algorithm assigns from becoming exponentially long is to just replace them with 1, 2, ... at each round. You (probably) don't need to know exactly what label each vertex has; rather, you (probably) just need to know whether two vertices have the same label or not.

Answer 2

Although the question is somewhat different, the following answer by Yuval Filmus also answers my question:

There are two non-isomorphic graphs with 16 vertices in which each vertex has 6 neighbors and 9 vertices at distance 2: the Shrikhande graph and the $4\times 4$ rook's graph.