Problem of the Week 899

Circles Need Four Colors

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.

16 November 1999