A 3-coloring is a way of assigning one of the three colors 0, 1 and 2 to all vertices in a graph so that no vertex has the same color as any of its closest neighbors. The graph that is colored here is a square or cubic lattice with fixed boundary conditions. A 3-coloring is also equivalent to an antiferromagnetic 3 state Potts model at zero temperature. Sometimes models of this type have a height function, that can be very useful when the model is analysed. The height function of a 3-coloring is defined as follows: Assign an integer height value to one vertex and propagate the height out from that vertex to the rest of the lattice. When you move from one vertex to one of its neighbors and the color changes as if you added 1 modulo 3 the height increases by one and if the color changes as if you subtracted 1 modulo 3 the height decreases by 1.
0 -> 1, 1 -> 2, 2 -> 0 : Delta_h = +1
1 -> 0, 2 -> 1, 0 -> 2 : Delta_h = -1
It is easy to see that it is possible to reconstruct the 3-coloring from the height function as the color of a vertex is simply its height value modulo 3.
Examples of 3-coloringsClick on the thumbnails to see larger versions of the images.
- Square lattice
A random 3-coloring created with CFTP.
The same 3-coloring, but with the frozen region removed. The border appears to be approximately circular. An example of an "Arctic circle" phenomenon.
- Cubic lattice
Center slize of 3-coloring created with CFTP.
The unfrozen region of a random 3-coloring.
The unfrozen region of a random 3-coloring with a more restrictive boundary condition.