The Earth-Moon Coloring Problem

We consider maps on two spheres, say the earth and the moon. Each simply connected region on the earth is a *country* and has a corresponding simply connected *colony* on the moon. We desire to color the countries and colonies so that:

- 1) each country receives the same color as its colony, and
- 2) if two countries or colonies share a common boundary, then they receive distinct colors.

Ringel [R] asked for the following earth-moon coloring number.

**Question:*** What is the minimum number of colors necessary to color all earth-moon maps? *

Ringel remarked that this number is between 8 and 12. The lower bound is easily demonstrated by drawing 8 states, any one adjacent to any other on either the earth or the moon. The upper bound follows from Euler's formula similar to the method used to prove the six-color planar graph theorem.

The dual form of the problem asks for the maximum chromatic number among all graphs of thickness two (a thickness-two graph is one having an edge partition into two planar graphs, one on the earth and one on the moon). As mentioned above, the complete graph *K(8)* is of thickness two. Beineke and Harary showed that *K(9)* is not the union of two planar graphs. However, Sulanke (as reported in [G]) showed that *C(5)+K(6)* is of thickness 2; clearly this graph is of chromatic number 9. Hence the earth-moon coloring number lies between 9 and 12.

The problem generalizes to ask for the maximum chromatic number of all graph of thickness *t*. Again, an upper bound of *6t* is shown by Euler's formula. The known formula for the thickness of the complete graph (cf [BW]) gives a lower bound of *6t-2*.

**Question:*** What is the maximum chromatic number among all graphs of thickness t? *

[Note added by Dan Archdeacon: Joan wrote an excellent paper [H] including this topic. It won the Allendoerfer award for Math. Magazine and I strongly recommend reading it.]

**References**

[BW] L. W. Beineke and A. T. White, Topological Graph Theory, Selected Topics in Graph Theory, L. W. Beineke and R. J. Wilson, eds., Academic Press, 1978, 15-50.

[G] M. Gardner, Mathematical Games, Scientific American 242 (Feb. 1980), 14-19.

[H] J. Hutchinson, Coloring ordinary maps, maps of empires, and maps of the moon, Math. Mag. **66** (1993) 211-226.

[R] G. Ringel, Fabungsprobleme auf Flachen und Graphen, VEB Deutscher Verlag der Wissenschaften (1950).

Submitted by: Joan P. Hutchinson, Department of Mathematics and Computer Science, Macalester College, St. Paul MN, USA 55105 [Additional material supplied by Dan Archdeacon]

Send comments to *dan.archdeacon@uvm.edu*

August, 1995