4-Colouring of Cartesian Grid with Diagonals

In this example, the objective is to 4-colour a graph that has nodes laid out on a regular Cartesian grid and that has edges between nearest-neighbours along both axes and also along the diagonals. Such a graph has a chromatic number of 4. The following images shows a fragment of such a graph, randomly coloured.

The parameters in the net generation panel can be set as follows:

The following images show an initial, random colouring and the colouring produced by the Conservative Fixed Probability Colourer (activation=0.3) after 50 steps. Unlike in the 2-colouring example, there does not appear to be strong region formation; rather, the conflicts quickly evaporate, leaving behind a few that perform quasi-random walks along fixed paths and occasionally intersect and resolve.

Step 0
Step 50

However, it may be more accurate to say that the regions do indeed occur, but they are not strictly incompatible so their borders are fuzzier and less noticeable.

The performance of CFP with activation 0.3 (CFP0.3), Sequential Hill Climber with tolerance 0.05 (SHC0.05) and Random Order (RO) are compared in the plots below, which show Gamma versus steps (on a log scale) and Gamma versus cost. As in the 2-colouring example, it may be observed that CFP is much faster at improving the colouring quality, but incurs higher cost than SHC.