The empire problem, also known as the m-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 m disjoint regions. Heawood (1890) showed that 6m colors are sufficient, and for the case m=2, 12 colors are also necessary (Gardner 1997; Frederickson 2002, pp. 31-32).