  Petford and Welsh introduced a sequential heuristic algorithm for
(approximately) solving the NP-hard graph coloring problem. The algorithm is
based on the antivoter model and mimics the behaviour of a physical process
based on a multi-particle system of statistical mechanics. It was later shown
that the algorithm can be implemented in massively parallel model of
computation. The increase of processing power in recent years allow us to
perform an extensive analysis of the algorithms on a larger scale, leading to
possibility of a more comprehensive understanding of the behaviour of the
algorithm including the phase transition phenomena.
