Hosted by The Math Forum

Problem of the Week 899

Circles Need Four Colors

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

A "general collection" of unit circles in the plane is a collection of circles of unit radius such that no three pass through a common point and no two are tangent.

If you draw 3 general circles in the plane, then the "circle graph" -- the graph formed by taking their intersection points as vertices and the obvious arcs as edges -- is 3-colorable. The same is true for collections of 4 circles. Find a general collection of unit circles in the plane so that the circle graph requires 4 colors.

Notes: A "coloring" of a graph is an assignment of colors to vertices so that adjacent vertices get opposite colors.

Source: suggested by Joan Hutchinson, Macalester.
© Copyright 1999 Stan Wagon. Reproduced with permission.

[Privacy Policy] [Terms of Use]

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

© 1994- The Math Forum at NCTM. All rights reserved.

16 November 1999