An arrangement of entangled squares

A solution for $k=4$ colors can be constructed from the arrangements of squares that square the square in the followig way: if an square has a corner in common with the bounding square and is neighbor to only 3 inner squares, then split the neighboring square whose corners are strictly inside the bounding square into four equal parts.

That is illustrated with A. J. W. Duijvestijn’s smallest squared square.
the squares with sidelengths 33 and 27 are only neighbors to 3 other squares; splitting inner squares with sidelengths 4 and 8 makes all squares neighbors of at least 4 other squares; increasing the size of each square by $epsilon$ while preserving the location of their centers makes each square overlap with at least four others.
If we take as vertices of a planar graph the squares and as edges pairs of overlapping squares, then a vertex coloring of that graph yields a coloring of the squares such that no overlapping pair has the same color.

enter image description here

one of the possible 4-colorings of the squares that remains valid after a slight center-preserving enlarging of the squares

enter image description here

The smallest satisfying arrangement of squares from which a satisfying example can be obtain by slightly enlarging the squares of the arrangment:

enter image description here

Leave a Comment