Importance: Medium ✭✭
 Author(s): Ringel, G.
 Subject: Graph Theory » Coloring » » Vertex coloring
 Keywords:
 Posted by: fhavet on: March 6th, 2013
Problem   What is the maximum number of colours needed to colour countries such that no two countries sharing a common border have the same colour in the case where each country consists of one region on earth and one region on the moon ?

In term of graphs, it can be rephrased as follows. What is the maximum chromatic number of a graph which is the union of two planar graphs (on the same vertex set)?

If a graph on vertices is the union of two planar graphs, then it has at most edges, and so it is has a vertex of degree at most . An easy induction shows that is 12-colourable, as observed by Heawood [He]. Gardner [G] reported an example requiring 9 colours (the join of and ). It is not known if configurations exist requiring 10, 11, or 12 colours.

More generally, one may ask for the maximum chromatic number of the union of planar graphs.

Problem   What is the maximum chromatic number of a graph which is the union of planar graphs?

The same reasoning as above shows that colours are always sufficient. The minimum number of planar graphs to decompose a complete graph [BW] gives a lower bound of for .

Bibliography

[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, 15-50, 1978.

[G] M. Gardner, Mathematical Recreations: The Coloring of Unusual Maps Leads Into Uncharted Territory. Sci. Amer. 242, 14-22, 1980.

[He] P.J. Heawood, Map Colour Theorems. Quart. J. Pure Appl. Math. 24, 332-338, 1890.

*[R] G. Ringel, Färbungsprobleme auf Flachen und Graphen. Berlin: Deutsche Verlag der Wissenschaften, 1959.

* indicates original appearance(s) of problem.