 Colour refinement

Colour refinement repeatedly separates vertices of a graph according to the colours of their neighbours. Its colours are labels for classes of vertices with the same currently visible structure; they are not a proper vertex colouring requiring adjacent vertices to differ. In individualization-refinement graph search, colour refinement reduces ambiguity before the algorithm branches.^[ref]

Let $c_t(v)$ be a vertex's colour after round $t$. One conceptual update assigns a common new colour exactly when both the previous colour and neighbour-colour multiset agree:The encoding must give distinct labels to distinct signatures. Retaining $c_t(v)$ prevents old classes from merging. When no class splits, the resulting partition of a set is an equitable partition: vertices in the same cell have equal numbers of neighbours in every cell.

For an original example, start all vertices of the six-vertex path graph $1-2-3-4-5-6$ with the same colour. The first round separates endpoints $\{1,6\}$ from internal vertices $\{2,3,4,5\}$. The next separates $\{2,5\}$, which each have an endpoint neighbour, from $\{3,4\}$, which do not. The three cellsare then stable. Reflection of the path exchanges the two vertices in each cell, so the remaining pairs are compatible with a genuine graph automorphism.

Colour refinement is invariant under vertex relabeling. To compare two graphs, colour signatures must be encoded consistently across both, for example by refining their disjoint union of graphs with shared initial colour meanings. A different count of vertices in a resulting colour class certifies graph non-isomorphism.

Agreement is weaker than isomorphism. Starting with one colour, both the complete bipartite graph $K_{3,3}$ and the triangular prism graph remain one six-vertex cell because every vertex has three neighbours. Yet the prism has triangles and $K_{3,3}$ has none. This failure motivates individualizing vertices and searching further; stable colour classes are not, in general, proof that all their vertices are related by graph automorphisms.