An amenable graph is a finite graph 
for which color refinement
distinguishes 
from every nonisomorphic graph 
(Arvind et al. 2017).
Equivalently, 
is amenable if and only if its Weisfeiler-Leman
dimension is 1, since color refinement is the one-dimensional Weisfeiler-Leman
algorithm. Arvind et al. (2017) characterized amenable graphs and showed
that the class can be recognized in time 
for a graph with 
vertices and 
edges.
