  Color refinement is a crucial subroutine in symmetry detection in theory as
well as practice. It has further applications in machine learning and in
computational problems from linear algebra. While tight lower bounds for the
worst case complexity are known [Berkholz, Bonsma, Grohe, ESA2013] no
comparative analysis of design choices for color refinement algorithms is
available. We devise two models within which we can compare color refinement
algorithms using formal methods, an online model and an approximation model. We
use these to show that no online algorithm is competitive beyond a logarithmic
factor and no algorithm can approximate the optimal color refinement splitting
scheme beyond a logarithmic factor. We also directly compare strategies used in
practice showing that, on some graphs, queue based strategies outperform stack
based ones by a logarithmic factor and vice versa. Similar results hold for
strategies based on priority queues.
