Rod Fletcher sent the following to me about coloring maps made up of only rectangles:
How many colors are required to color a map consisting of only rectangular regions?
Contrary to the usual map coloring rules, let us add the requirement that even two regions that are touching at a corner must have different colors.
The Four Color Theorem does not apply because its rules imply that the map can be represented as a planar graph,
while the rule described above can result in graphs that are non-planar.
Indeed, the argument below shows that some maps consisting of rectangular regions require five colors. However, this does not imply that five colors are sufficient, but only that five colors are necessary.
By definition, four squares touching at a point require four colors.
We proceed by assuming that only four colors are needed for any map.
Let the four squares be surrounded by eight regions as shown below. Once a color is chosen for any side (i.e., a rectangle lying between two corner squares),
then the colors for the three remaining sides are uniquely determined. After the sides are colored, the colors for the corner squares are determined.
Each side of the whole square now presents three different colors. Let two more regions be added to both the left and right sides as shown below.
The two longer rectangles are each touching three different colors, so their colors are thus determined. Next, the colors of the two corner squares (A and E) are determined.
Finally, any region that touches all five regions on the bottom (A through E) will be touching all four colors. Hence, a fifth color is needed for that region, which contradicts the initial assumption. QED.
Anyone who is motivated to tackle this problem might start by reading Wikipedia's article on 1-planar graphs.
The graph corresponding to a map with rectangular regions, per the rules described above, is 1-planar.
However, it happens to be a special case of a 1-planar graph that is not addressed in that article. The article does, however, state that 6 colors are sufficient for the general 1-planar graph,
so if the answer to the present question is not 5, then it must be 6.
Rod updated this page with an example that involves the special case of rectangles in the shape of dominoes (i.e., a 2:1 aspect ratio).
Even in this restricted case, he found that, in general, 5 colors are needed. Click on one of the following to see his work:
Click here to download the PDF file
Click here to download the PowerPoint presentation
If the PDF is displayed rather than downloaded, it should be manually saved and then viewed in a manner that displays just one page at a time.
Stepping through the pages will then show the incremental changes in the coloring more 'graphically'.
Rod adds this challenge:
The example illustrated in the dominoes is rather big. Is there a smaller configuration that can likewise be proven to require 5 colors?
If you discover one, please send it to me at the email address below.