Post #1552729

2026-04-14 13:39 UTC

For #TilingTuesday, 4-colourings of the Penrose P2 and P3 tilings, via refinements of their substitution systems. Penrose tilings must _admit_ proper 4-colourings, by the Four Colour Theorem and the Erdős–de Bruijn theorem. 4CT says that any finite patch of a given plane tiling must have a 4-colouring; EdB says, in that case, so does the whole plane. But EdB doesn&#39;t provide an efficient algorithm for constructing such a colouring; it only guarantees that one exists in principle. If you wanted a large patch of 4-coloured tiling, you might have to generate a finite patch first, and then run one of the horrible algorithms from proofs of 4CT. And once you&#39;d done it, there&#39;d be no guarantee that _that_ 4-coloured patch would extend to a 4-colouring of the whole plane. What you want is a refined substitution system, containing multiple types of each Penrose tile shape, each already equipped with a colour. Then you could generate tilings efficiently from that, and you&#39;d know you had not just a finite coloured patch, but a finite patch from a whole coloured plane. For P3 (rhombs) this is easy. Split each rhomb into a subtype for each of its 10 rotations. The adjacency graph on those 20 classes has no self-edges. There&#39;s no reason to expect that graph to be _planar_, but it turns out it can be 4-coloured anyway. So you can 4-colour a P3 tiling by assigning colours based only on tile shape and orientation. For P2 (kites and darts), if you make the same graph, it doesn&#39;t admit a 4-colouring. But as part of my transducers research, I wrote code to refine a substitution system further, by classifying each tile based on its immediate neighbours. If I classify the P2 tiles by orientation and _then_ run a pass of that refinement algorithm, it generates 50 subtypes of kite and 40 subtypes of dart, and the adjacency graph for _those_ classes is 4-colourable. So it takes a bit more work, but it&#39;s still a substitution system that directly delivers a 4-coloured P2 tiling. The pictures here are derived from those two refined substitution systems. In each case, the 4-colouring of the class graph was done by brute force: SageMath&#39;s first_coloring() function. So the colours aren&#39;t optimised for aesthetics!

Replies (3)

@simontatham@hachyderm.io 2026-04-14 13:40

In fact P3 rhomb tilings have been proven to be _three_-colourable. This is also true of any edge-to-edge plane tiling with parallelograms: a bit of reasoning about angle sums shows that the border of any finite patch must include a tile with at most 2 neighbours, so you can inductively 3-colour the rest of the patch and then you're guaranteed to be able to pick a colour for that last tile. And then, again, Erdős–de Bruijn says a three-colouring of the whole plane must exist. But again that proof doesn't come with any algorithm for delivering a specific three-colouring known to extend to the whole plane. I tried to use the same brute-force approach to generate a three-coloured P3 substitution system, by running multiple passes of my refiner starting from the orientation-classified version of P3. No luck: after two refinement passes the graph still had chromatic number 4, and after three, it became too big to wait for Sage to try to colour it at all. I'd _like_ a 3-coloured refinement of the P3 substitution system, but I haven't yet found a way to construct one, by this technique or any other!

Open ##2400400
@simontatham@hachyderm.io 2026-04-15 08:19

It's not Tuesday any more, but here are a few more bonus pretty pictures. There's a clever construction called the "Wieringa roof" in which you assign every vertex of a P3 rhomb tiling a z-coordinate in {1,2,3,4}, with each rhomb having coordinates either 1,2,3,2 or 4,3,2,3, so that the tiling is lifted out of the flat plane into a crinkly surface. With the right scale factor this turns the two rhomb types into the _same_ shape of 3D rhombus, just tilted at different angles to the horizontal. So another way you can classify tiles in a P3 tiling is by their Wieringa height: do they have a vertex at the minimum height 1, or one at the maximum height 4? (Every tile has exactly one of these.) If you distinguish P3 tiles as low vs high _and_ by their 10 orientations, then it's not only possible to four-colour the adjacency graph, but to do it in such a way that every tile is a different colour from the other tile type at the same orientation (counting "same orientation" as the vector toward the extreme vertex from the opposite one), _and_ from the 180° rotations of both. This gives an almost balanced colouring (the density of the colour classes only vary by about 10%) and I think it looks much nicer than the previous version. You can assign vertex heights in the same kind of way to a P2 tiling, by considering its half-deflation to P3. That doesn't give you a nice 3D structure (the tiles would end up non-planar), but it still lets you classify kites and darts into two types each. With that and orientation, the adjacency graph still isn't four-colourable, but we can refine by neighbourhood as before, and again end up with a colouring that's better balanced and has fewer obvious regularities (though still a few). Here are the same two pictures as in the previous post, recoloured using these slightly nicer systems. As a bonus, I've also rendered the same two tilings by colouring _only_ by Wieringa height, so that you can see the rather nice patterns made by the high tiles and the low tiles.

Open ##2400401
@petermilley@zeroes.ca 2026-04-14 15:05

@simontatham@hachyderm.io dumb question: P3 is related to tesseract tilings of 5-space, so do the 2-cells of the tiling of 5-space admit a 4-colouring? It feels like the answer should be obviously yes or obviously no but I'm rusty at this.

Open ##2400404