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]