Color refinement is an iterative graph coloring algorithm used to distinguish graphs that are not isomorphic. Starting with all vertices the same color, each iteration recolors every vertex according to its current color and the multiset of colors of its neighbors. The process stops when its color classes no longer split, producing a stable coloring.
To compare graphs and
, color refinement is applied
to their graph disjoint union. It distinguishes
the graphs if some final color occurs a different number
of times in
and
(Arvind et al. 2017). Color refinement is equivalent to the one-dimensional
Weisfeiler-Leman algorithm. Consequently,
a finite graph has Weisfeiler-Leman
dimension 1 iff it is an amenable
graph.