This is motivated by the new paper of Smith, Myers, Kaplan, and GoodmanStrauss, wherein they define the existence of an aperiodic monotile. Clearly their tiling is not threecolorable, so we have from Appel and Haken (1977) that its chromatic number is 4. What is not clear to me, however, is how one could algorithmically construct such a coloring. Any suggestions would be much appreciated!

$\begingroup$ Do you have a quick proof that threecolorability fails? It took me filling out a moderately large patch before I reached a contradiction. $\endgroup$– RavenclawPrefectCommented Mar 25, 2023 at 3:41

3$\begingroup$ The threecoloring question was asked and answered at Can we threecolor a tiling of the plane with Smith, Meyers, Kaplan, and GoodmanStrauss's einstein? $\endgroup$– Gerry MyersonCommented Mar 25, 2023 at 4:37
5 Answers
I tried to find a colouring where one of the colours comprised exactly the 'flipped' tiles. So I coloured all of the flipped tiles blue and then found three of the remaining tiles which were all touching and coloured them red, yellow and green arbitrarily. After this I found that I could keep expanding the colouring by finding an uncoloured tile that was touching two of red, yellow and green, and colouring it with the third colour. I never had to make any choices, so it seems that there is a unique colouring such that one of the colours comprises exactly the flipped tiles.
If this is true then the colouring is trivial to perform algorithmically, but I don't yet have a complete proof.
Look at the reduction to an hexagonal grid shown in Figure 2.2 of the original paper.
The hexagonal grid is formed by merging each flipped tile with a neighbour. The hexagonal grid is strictly more connected than the unflipped tiles (i.e. there are hexagons that touch even though their corresponding tiles don't). So the unique 3colouring of the hexagonal grid does indeed yield a 4colouring of the original tiling.
It remains to show that this colouring is the unique such.
Added 20230614: The new Spectre tiling does not involve any flipped tiles. However we can still produce a similar colouring. Some of the tiles are special in that their rotation is an odd multiple of $2\pi/12$ relative to the others. Colouring these tiles in blue, the remainder can again be three coloured in a unique way.

2$\begingroup$ Jesse Clark has the same colouring here: twitter.com/myhf/status/1639053012399439872. They didn't notice that the flipped tiles are all the same colour, but did point out that four tiles meeting at a point all have different colours. $\endgroup$ Commented Mar 25, 2023 at 9:16

$\begingroup$ Nice! Is there a wallpaper group hiding in the first image? $\endgroup$– Mark SCommented Mar 25, 2023 at 13:30

1$\begingroup$ @MarkS If you squint a bit, you can see that the red, yellow and green tiles form hexagonal grids with the same angle and spacing, while the blue tiles form a hexagonal grid with a different angle and larger spacing. My guess would be that the constants relating the two grids are irrational, killing any wallpaper group. $\endgroup$ Commented Mar 25, 2023 at 15:59

$\begingroup$ I think it is worth to point out that the "special" tiles in Spectre tiling are not arbitrary  in the Hat tiling, you can smoothly change a parameter to get a spectrum of aperiodic tiles; Hat and Turtle are popular ones, and Spectre is one of the shapes in this spectrum (which happens to admit different tilings if mirroring is allowed). The same operation can be done with Spectre tiling, but (except the Spectre parameter) you get two different shapes, for example, you get both Hats and Turtles. So this is where the "special tiles" come from. $\endgroup$ Commented Mar 14 at 10:21
I think there's no obstruction to just greedily choosing a working color by going outwards in a spiral:
Each new tile never borders more than three precolored neighbors.

1$\begingroup$ Nice suggestion. But can this be proved? $\endgroup$– David Roberts ♦Commented Mar 25, 2023 at 6:24
The bijection between nonreflected tiles and a hexagonal tiling is the way to go. To construct it, we can associated to the hat tile a corresponding hexagonal tile, so that a tiling of hats gives a partial tiling of hexagons:
This partial tiling, minus the reflected tiles, has a natural decomposition into 'triangles' constructed from hexagons, of side length 1, 2 or 3, which slide together to form a full tiling. This is probably best understood by interacting with this p5js sketch.
In a some more detail, write $T_{hex}$ for the hexagon associated to a hat tile $T$, and $T_{hex}^o$ for $T_{hex}$ minus its vertices, and call a tile face up if it is isometric to a rotation + translation of the tile above, and face down otherwise (likewise for the corresponding hexagons, which we'll colour purple and orange respectively). Then one can show that for a tiling $X$ of hats, each connected component of $\cup \{T_{hex}^o  T \in X, T\text{ face up}\}$ is constructed in one of the following three ways:
In addition, let arrows denote the 'triangle vertices' of the 2 and 3triangles
Then these hexagons are adjacent or almost adjacent to reflected tiles, in the sense illustrated below.
(it turns out that the vertices of the 3triangle are always adjacent to reflected tiles, but we do not need this fact here)
The 1triangle is either adjacent to 3 reflected tiles, or almost adjacent to 3 reflected tiles, as illustrated below.
Since any partial tiling $X_{hex}$ of hexagons coming from a tiling of hats contains a face up hexagonal tile adjacent to a face down hexagonal tile, we can assume WLOG that $X_{hex}$ contains a patch of the form:
Proposition: such a patch is part of a larger neighbourhood:
Note that the 1 and 2triangles shown above may form part of larger hex triangles.
Consider the following lines on these neighbourhoods (for convenience, we also include the patch rotated by 𝜋/3).
The red and blue curves can be extended arbitrarily far in either direction. For example, moving from left to right along the red curve in patch A, we end up traversing the top edge of a 2 or 3triangle. The top right vertex of this triangle must be adjacent or almost adjacent to a face down hexagon, which means the top edge coincides with the top edge of the triangle on the lower left of the diagram in patch A or B, respectively, and thus the red curve can be extended further to the right.
Thus we can construct three families of curves, each of which divides the hexagons into 'ribbons' indexed by $\mathbf{Z}$. We can use these indices to define translations of all hexagons that result in the simultaneous Tetrislike move in the interactive sketch linked above.
Incidentally, the orientations of $\{T_{hex}  T \text{ face down}\}$ appear to behave similarly (at least qualitatively), so there may be a hierarchy of hat and hex tilings (possibly alternating between face up and face down dominant tiles)
Here are some computable colorings discovered by Simon Tatham. The algorithm is described at Appendix: fourcolourings of the Hats and Spectre tilings.
Hat
Spectre
This tiling and colouring has translation symmetry (bold dashed line) and point symmetry (red dots and thin dashed lines). No point symmetry for the tiles under the translation axis. But it cannot tile the whole plane. It's only a frieze as one cannot continue the tiling beyond the red lines. One gets holes and/or overlap. I could not keep the same colours for the flipped tiles (bold boundary) under the translation axis as Oscar Cunningham did. Here too four tiles touching one point (can) have 4 different colours (the flipped yellow tiles can as well be cyan). Perhaps that's a sufficient rule.

1$\begingroup$ The question is asking about the tiling of the whole plane, given in the reference, though. $\endgroup$– David Roberts ♦Commented Mar 27, 2023 at 20:48

$\begingroup$ If it bothers more than it helps, please delete it. $\endgroup$ Commented Mar 28, 2023 at 7:33

$\begingroup$ Well, it would be useful if there were some comments that indicated how this can help address the original question, otherwise it's not clear iwhat the OP can do with this answer. $\endgroup$– David Roberts ♦Commented Mar 28, 2023 at 11:21

1$\begingroup$ Is Appel & Haken's proof still applicable to an infinite aperiodic graph ? Such a graph with 1 region less still remains an infinite graph, right? How to apply the reduction principle then? $\endgroup$ Commented Mar 31, 2023 at 8:03

1$\begingroup$ @P. that might make a good standalone question! $\endgroup$– David Roberts ♦Commented Mar 31, 2023 at 9:37