Hosted by The Math Forum

# A Three Color Theorem?

Spring 99 Archive || MacPOW Home || Math Forum POWs || Search MacPOW

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.

NOTES:

• Maps are assumed to be in the plane.
• The exterior region (the "ocean") need not be counted as a country.
• A coloring must use different colors on countries that share an edge.
• "Meet edge-to-edge" means that any pair of countries that meets does so either in a single point or a full edge of each country.
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
---------------- ----------------
```

#### MOTIVATION:

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.

[Privacy Policy] [Terms of Use]

© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/

16 February 1999