Empire Problem

The empire problem, also known as the -pire problem) asks for the maximum number of colors needed to color countries such that no two countries sharing a common border have the same color (this is the usual four-color theorem) in the case where each country consists of  disjoint regions. Heawood (1890) showed that  colors are sufficient, and for the case , 12 colors are also necessary (Gardner 1997; Frederickson 2002, pp. 31-32).

REFERENCES

Frederickson, G. N. Hinged Dissections: Swinging & Twisting. New York: Cambridge University Press, 2002.

Gardner, M. The Last Recreations: Hydras, Eggs, and Other Mathematical Mystifications. New York: Springer-Verlag, 1997.

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