Heawood's empire problem
type: Item
instance of: scholarly article
title: Heawood's empire problem
zbMATH Open document ID: 0574.05020
DOI: 10.1016/0095-8956(85)90082-6
author: Brad Jackson
author: Gerhard Ringel
published in: Journal of Combinatorial Theory. Series B
publication date: 1985-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C10
zbMATH DE Number: 3916297
zbMATH Keywords: Euler characteristic
zbMATH Keywords: method of current graphs and cascades
zbMATH Keywords: m-pire
zbMATH Keywords: chromatic number
zbMATH Keywords: Klein bottle
reviewed by: Ioan Tomescu
MaRDI profile type: Publication
full work available at URL: 0095-8956(85)90082-6
OpenAlex ID: W2023410066
cites work: The existence of unavoidable sets of geographically good configurations
cites work: Every planar map is four colorable. II: Reducibility
cites work: Maps of m-pires on the projective plane
cites work: The splitting number of the complete graph
cites work: Solution of Heawood's empire problem in the plane.
cites work: Q3261867
cites work: Q4773723
description: scientific article; zbMATH DE number 3916297