Name
Abstract | ||
|---|---|---|
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 [(6r+1+root(6r+1)(2)-24 epsilon)/2] colors, where epsilon is the Euler characteristic of F-2. Also, he conjectured that this is best possible except for the case (epsilon,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 r3 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 (4r+1+root(4r+1)(2)-16 epsilon)/2] colors. Moreover, we conjecture that this is best possible except for the cases (epsilon,r)=(2,1),(0,1),(-2,1). We prove it for the cases epsilon=2,1,0 with r >= 2. (C) 2013 Wiley Periodicals, Inc. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1002/jgt.21717 | JOURNAL OF GRAPH THEORY |
Keywords | Field | DocType |
empire problem,even embedding | Topology,Combinatorics,Colored,Embedding,Disjoint sets,Klein bottle,Torus,Euler characteristic,Projective plane,Conjecture,Mathematics | Journal |
Volume | Issue | ISSN |
75.0 | 1.0 | 0364-9024 |
Citations | PageRank | References |
0 | 0.34 | 3 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Kenta Noguchi | 1 | 0 | 0.68 |