Color refinement is an iterative graph coloring algorithm used to distinguish nonisomorphic graphs. 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.
To compare graphs 
and 
,
color refinement is applied to their 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 if and only if it is an amenable graph.
