The Empire Problem in Even Embeddings on Closed Surfaces

Let M be a map on a closed surface F 2 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 F 2 . In 1890, Heawood proved that the countries of M can be properly colored with ⌊ ( 6 r + 1 +( 6 r + 1 ) 2 − 24 ɛ ) / 2 ⌋ colors, where ε is the Euler characteristic of F 2 . Also, he conjectured that this is best possible except for the case ( ɛ , r ) = ( 2 , 1 ) , and prove for the case (2, 2). In 1959, Ringel proved the conjecture for the case where F 2 is the torus and r = 2 . In 1980 and 1981, Taylor proved it for the cases (2, 3), (2, 4), and where F 2 is the torus. In 1983 and 1984, Jackson and Ringel proved it for the cases where F 2 are the projective plane and the sphere. The case where F 2 is the Klein bottle was resolved for r ≥ 3 by Jackson and Ringel in 1985 and for r = 2 by Borodin in 1989. We call a graph on F 2 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 F 2 and prove that it can be properly colored with ⌊ ( 4 r + 1 +( 4 r + 1 ) 2 − 16 ɛ ) / 2 ⌋ colors. Moreover, we conjecture that this is best possible except for the cases ( ɛ , r ) = ( 2 , 1 ) , ( 0 , 1 ) , ( − 2 , 1 ) . We prove it for the cases ɛ = 2 , 1 , 0 with r ≥ 2 .