 Individualization-refinement graph search

Individualization-refinement graph search explores possible vertex labelings while repeatedly distinguishing vertices by their adjacency structure. It combines inexpensive colour refinement with branching when refinement leaves indistinguishable vertices. This is a framework for canonical graph labeling and graph automorphism computation, rather than a claim that degree information alone decides graph isomorphism.^[ref]

Start with an ordered partition of a set of the vertex set, representing any prescribed vertex colours. Within each cell, compare the number of neighbours each vertex has in every current cell. Split a cell whenever those count vectors differ, and repeat until no further split occurs. The result is an equitable partition. A discrete partition of a set, with one vertex per cell, gives a candidate vertex ordering.

If a cell still has several vertices, choose a target cell by a rule preserved under relabeling. For each possible chosen vertex in that cell, make that vertex a singleton, refine again and continue recursively. The leaves provide candidate encodings of the adjacency matrix. Choosing a fixed extremal encoding over the complete search gives a canonical representative. Implementations use valid node invariants and discovered graph automorphisms to prune branches without changing the result.^[ref]

For an original example, label a six-vertex cycle graph temporarily as $0,1,\dots ,5$, with adjacency modulo6. Starting with one cell, every vertex has two neighbours, so colour refinement alone leaves one cell. Individualizing vertex0and refining givesVertices1and5remain indistinguishable because reflection fixing0exchanges them. Individualizing one of them resolves the remaining pairs. The temporary names explain the search; they cannot be used as invariant tie-breakers that silently discard the other possible labeling.

By contrast, two disjoint triangles also begin with six vertices of degree2, but after individualizing one vertex the refined cell sizes are1,2,3. The cycle's sizes are1,2,2,1. Thus this branch detects structure that initial degree refinement misses. Highly symmetric graphs can still require extensive search; refinement is a reduction of the search space, not a universal small bound on it.