The Empire Problem in Even Embeddings on Closed Surfaces
Kenta Noguchi · Journal of Graph Theory · 2013
Let M be a map on a closed surface F2 and suppose that each country of the map has at most r disjoint connected regions. Such a map is called an r-pire map on F2. In 1890, Heawood proved that the countries of M can be properly colored with colors, where ε is the Euler characteristic of F2. Also, he conjectured that this is best possible except for the case , and prove for the case (2, 2). In 1959, Ringel proved the conjecture for the case where F2 is the torus and . In 1980 and 1981, Taylor proved it for the cases (2, 3), (2, 4), and where F2 is the torus. In 1983 and 1984, Jackson and Ringel proved it for the cases where F2 are the projective plane and the sphere. The case where F2 is the Klein bottle was resolved for by Jackson and Ringel in 1985 and for by Borodin in 1989. We call a graph on F2 an even embedding if it has no faces of boundary length odd. In this paper, we consider the r-pire maps whose dual graphs are even embedding on F2 and prove that it can be properly colored with colors. Moreover, we conjecture that this is best possible except for the cases . We prove it for the cases with .