Heawood's empire problem (Q1062996)

In a map on a surface a certain collection of m disjoint connected countries is said to be an m-pire. In coloring a map all components of a given empire must receive the same color and, of course, two adjacent empires must receive different colors. Let S be a closed surface with Euler characteristic E and let \(\kappa\) (S,M) be the smallest number k of colors such that every map on S, where each empire has at most M components, is colorable by k colors. \(\kappa\) (S,M) is called the M-pire chromatic number of S. With the exception of \(M=1\) and \(E=2\) (four color problem) Heawood showed in 1890 that \[ (1)\quad \kappa (S,M)\leq \lfloor \frac{1}{2}(6M+1+\sqrt{(6M+1)^ 2-24E)}\rfloor \] holds. Haken and Appel have shown (1) in the remaining case \(M=1\) and \(E=2\). Heawood conjectured that equality always holds in (1). It has been shown by Franklin that equality in (1) does not hold when S is the Klein bottle and \(M=1\). Some partial affirmative answers to this problem have been obtained by Heawood, Ringel, Youngs, Jackson and Taylor. In this paper it is proved that equality holds in (1) in the following cases: (i) S is a connected nonorientable surface and the right side of (1) is congruent to 1, 4, or 7 modulo 12 (for the Klein bottle for \(M\geq 3\) only); (ii) S is a connected orientable surface, M is even, and the right side of (1) is congruent to 1 modulo 12; (iii) S is a connected orientable surface, M is odd, and the right side of (1) is congruent to 4 or 7 modulo 12.