= 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.<Practical graph isomorphism, II by Brendan D. McKay and Adolfo Piperno>[Section3.1, equitable refinement and Algorithm1]{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:
$$
c_{t+1}(v)=\operatorname{encode}\!\left(c_t(v),\{\!\{c_t(u):u\sim v\}\!\}\right).
$$
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 cells
$$
\{1,6\},\quad\{2,5\},\quad\{3,4\}
$$
are 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>.
Back to article page
