We start with an uncoloured copy of the Petersen graph, and lists of three colours (blue, green, violet) for each vertex. The colouring is constructed in two phases, each consisting of random steps.
In phase 1 the goal is to find a flawless partial colouring. A vertex is considered flawed if it is uncoloured and either there are too few colours available to properly colour it given the colours on its neighbours, or if one of its available colours is also available for too many neighbours. Uncoloured vertices appear white, and flawed vertices appear with a red border. There is a technical definition of “too many” that we leave to the academic paper. Clicking or tapping a vertex will resample the partial colouring on its neighbourhood, and doing this on flawed vertices is likely to fix the flaw. One can prove that with good probability it doesn’t take many attempts to reach a situation with no flawed vertices.
It is unlikely that you can colour the entire graph during phase 1, mostly because creating uncoloured vertices happens quite often. But when there are no flawed vertices it must be possible to complete the existing partial colouring, because of a careful definition of “flawed” and some nice combinatorial results. When there are no flawed vertices, click the button to enter phase 2. In phase 2 we look for a way of completing the flawless partial colouring found in phase 1.
For phase 2, every colour assigned at the end of phase 1 is fixed, and these vertices appear with a white border during phase 2. At the start of phase 2, random colours are chosen for all vertices that are uncoloured at the end of phase 1, in a way which is compatible with the fixed colours. These choices may create monochromatic edges amongst the vertices whose colours are not fixed, which are a new type of flaw that we consider during phase 2. Click a flawed edge to resample the colours of its endpoints in an attempt to fix the flaw. You have found a proper colouring if at any point during phase 2, there are no flawed edges.
Your chances of success change drastically with the number of colours. You can always succeed on the Petersen graph with 3 or more colours. For a random 4-regular graph this is true with at least 5 colours, and for 6-regular graphs 7 colours suffice.
Pressing the restart button will begin again with the currently specified graph options and number of colours.