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.
