Problem of the Week 880

A Three Color Theorem?

True or False: Every map whose countries are quadrilaterals that meet edge-to-edge can be 3-colored.

For example, a checkerboard is (a very simple example of) the sort of map we are considering. It can be 2-colored.


I should add that edge-to-edge includes the possibility that one quadrilateral meets another in TWO edges, which can happen if they are nonconvex.

To underscore that "full edges" means the following is not allowed:

---------------- -----------
                |Quad #1
    Quad #3     |   
                |  Quad #2
---------------- ----------------


The motivation will be explained next week. But I can here announce that Tom Sibley (St. Johns University) and I have just proved (by a VERY short proof!) that any (finite or infinite) Penrose rhomb tiling is 3-colorable. The Penrose kites and darts situation remains open, though it has been conjectured for almost 20 years that they too are 3-colorable. This week's puzzle arose in our work (and was solved by Rick Mabry (LSU/Shreveport)). Our coloring result is much more general than the Penrose case and details will be posted next week.

Late news: Michael Schweitzer has taken our proof and made it even shorter!

© Copyright 1999 Stan Wagon. Reproduced with permission.

16 February 1999