Hosted by The Math Forum


Problem of the Week 880

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:

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]

_____________________________________
Home || The Math Library || Quick Reference || Search || Help 
_____________________________________

© 1994-2014 Drexel University. All rights reserved.
http://mathforum.org/
The Math Forum is a research and educational enterprise of the Drexel University School of Education.The Math Forum is a research and educational enterprise of the Drexel University School of Education.

16 February 1999