Skip to main content
MathOverflow

Return to Answer

added a colorated arrangment derived from a squared square
Source Link
Manfred Weis
Manfred Weis
  • 13.2k
  • 4
  • 34
  • 76

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

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

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

enter image description here

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

provided a smaller example and fixed the description of coloring thr squares
Source Link
Manfred Weis
Manfred Weis
  • 13.2k
  • 4
  • 34
  • 76

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 centers of squares an let theand as edges connect the centerspairs of overlapping squares that are adjacent along a piece of their sides, then a vertex coloring of that graph yields a coloring of the squares such that each overlaps at least four of a differentno overlapping pair has the same color.

enter image description here

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

enter image description here

A solution 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 centers of squares an let the edges connect the centers of squares that are adjacent along a piece of their sides, then a coloring that graph yields a coloring of the squares such that each overlaps at least four of a different color.

enter image description here

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

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

enter image description here

Source Link
Manfred Weis
Manfred Weis
  • 13.2k
  • 4
  • 34
  • 76

A solution 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 centers of squares an let the edges connect the centers of squares that are adjacent along a piece of their sides, then a coloring that graph yields a coloring of the squares such that each overlaps at least four of a different color.

enter image description here