CHAPTER 8
MAPCOLORING
PROBLEMS
In this chapter we will see that the famous fourcolor theorem can be formulated  and studied  in graphtheoretical terms. Graph theory will be used to establish the fivecolor theorem. The Heawood Mapcoloring theorem will be introduced; this powerful theorem, whose proof was completed in 1968, answers the coloring question  which, at that time, was still unanswered for the sphere  for every other closed 2manifold. The easy half of the p r o o f  found by Heawood in 1890 is presented in this section. The difficult half of the p r o o f  developed primarily by Ringel and Youngs  will be discussed in Chapter 9. Consider any map of the world. Suppose we desire to color the countries of the world (or the states of a particular country, or the counties of a particular state, etc.) so that the distinct countries are distinguishable. This means that if two countries share a border at other than isolated points, then they must be colored differently. We make only one assumption as to the countries themselves: each country must be connected (this rules out Pakistan of some decades ago, and the United States, for example.) Note that a country need not be 2cell; that is, it may entirely surround some collection of other countries (such is the case for a certain region in France; see Fr~chet and Fan [EEl], p. 3). We mention in passing that several generalizations of this mapcoloring problem are possible. One of the most appealing is the following: allow disconnected countries, with each country having at most k components. (It is not hard to see that, without this restriction involving k, arbitrarily many colors may be needed.) Then it can be shown (see Problem 86 for the case k = 2) that 6k colors will always suffice. Ringel ([R10]; p. 26 (see also Heawood [H4])) displays a map, for the case k = 2, requiring 12 colors, so that this case is completely solved. Returning now to the case of classical interest (k  1), we pose the question thusly: what is the smallest number of colors needed to color any map on the sphere (or, equivalently, on the plane)? That four colors may be needed is indicated by the map induced by the tetrahedron. That five colors suffice for the sphere will be demonstrated shortly. Whether or not five colors are ever necessary has probably stimulated as much work in mathematics as any other single mathematical question; and the answer is finally known. The fourcolor theorem says that 89
90
8. M A P  C O L O R I N G P R O B L E M S
five colors are never necessary: four colors will suffice to color any map on the sphere. Many "proofs" of the four color theorem have been presented to the mathematical community, but most have not yet survived close scrutiny. The interested reader might wish to read through one of the false "proofs", given by Kempe in 1879 (see [BCL1], for example), and try to spot the error in the "proof." Graph theory enters the picture in the following way. Form the dual of the map in question. This produces a pseudograph. Attempt to color the vertices of the pseudograph so that no two adjacent vertices have the same color. The pseudograph has no loops, as no country ever shares a border with itself. In fact, we may as well drop any multiple edges, since they (the " extra" edges) have no bearing on the coloring question. Then the coloring numbers, or chromatic numbers, of the resulting graph and the map will be identical. This leads to the following definitions. 81. D e f i n i t i o n s a n d t h e S i x  C o l o r T h e o r e m Def. 81. The chromatic number, )t(G), of a graph G is the smallest number of colors for V(G) so that adjacent vertices are colored differently. Def. 82. The chromatic number, x(Sk), of a surface Sk is the largest x(G) such that G can be imbedded in Sk. We prove that six colors will suffice for every planar graph. Of course, both this result and the fivecolor theorem of the next section are subsumed by the FourColor Theorem. But we want to include the proofs, as the techniques they illustrate will have value later. T h m . 83. Six colors suffice to color any map on the sphere; that is, (So) <__6. PROOF. We use induction on p, the order of the planar graph G, to show that x(G) _< 6. The anchor for p = 1 is clear. So, assume that all planar graphs with p  1 vertices (p > 1) are 6colorable. Let G be planar, of order p. By Lemma 519, G has a vertex v of degree 5 or less. By the induction hypothesis, x ( G  v) <_ 6. Since the neighbors of v use at most 5 colors, there is a sixth color available for v. V1 82. T h e F i v e  C o l o r T h e o r e m The proof below is found in [BCL1].
83. THE FOURCOLOR T H E O R E M
91
T h m . 84. Five colors will suffice to color any m a p on the sphere; i.e. (s0) < 5. PROOF. We use the induction on p, the order of the graph G, to show that if "),(G)  0, then x(G) _< 5. The anchor at p = 1 is obvious. Now assume that all planar graphs with p  1 vertices (p > 1) are 5colorable. Let G be planar, with p vertices. By L e m m a 519, G contains a vertex v of degree 5 or less. By the induction hypothesis, x ( G  v) < 5; denote the colors in a 5coloring of G  v by 1,2,3,4,5. If not all five colors are used for the vertices adjacent to v in G, we can color v with one of the colors not so used, to give x(G) _< 5. Otherwise, d(v) = 5, and all five colors are used for vertices adjacent to v. We can assume that the situation around v is as in Figure 81, and that v~ is colored with color i. Consider now any two colors assigned to nonconsecutive vertices vi, say 1 and 3, and let H be the subgraph of G  v induced by all those vertices colored 1 or 3. If vl and v3 belong to different components of H, then by interchanging the colors in the component of H containing Vl, say, a 5coloring of G  v is produced in which no vertex adjacent with v is assigned the color 1, and we can use 1 for v. If, on the other hand, Vl and v3 are joined by a path in H, the above argument guarantees that we can recolor v2 with 4, and use 2 for v. This completes the proof. [21 V5 ?)4
Vl
F i g u r e 81. 83. T h e F o u r  C o l o r T h e o r e m In the notation of Section 81, the Fourcolor Theorem becomes: T h m . 85.
x(So)= 4.
The first proof is due to Appel and Haken [AH1] in 1976. See Woodall and Wilson [WW1], for one discussion of this proof; for a second proof, see[RSST1]. See also [SK1], for example. The proofs so far obtained for Theorem 85 are enormously more complicated than those of either Theorem 83 or 84, in part due to the positive difference upon subtracting the number of colors, four, from
92
8. MAPCOLORING PROBLEMS
the maximum minimum degree of a planar graph, five. Thus no simple induction argument seems to be available. In fact, the sphere is the only closed orientable 2manifold for which the maximum minimum degree is not obtained by a complete graph. (See Theorem 815.) The sphere is also the only closed orientable 2manifold of positive characteristic. This is why Theorem 813 does not contain a (simple) proof of the FourColor Theorem. There are many equivalent formulations of the Fourcolor Theorem. (See, for example, Ore's book: The Four Color Problem [O1], or [BCL1].) Of course, these are all now corollaries of the theorem itself. Following a definition, we present one of these. Def. 86. A graph G is said to be nedge colorable if n colors can be assigned to E(G) so that adjacent edges are colored differently. T h m . 87. Every cubic plane block is 3edge colorable. PROOF. Let G be a cubic plane block. By Theorem 85, G is 4region colorable; let the colors be taken from the group F  Z2 • Z2. Since G is a block, each edge x of G appears in the boundary of two distinct (but adjacent) regions, R~ and R 2. Define the color of x by c(x)  c(R~)+ c(R~), addition taking place in F. Since c(R~) ~ c(R~), c(x) ~ e, the identity of F (every element is its own inverse, in F.) Let x, y, and z be adjacent edges in G; see Figure 82. We claim that x, y, and z are colored distinctly. Suppose to the contrary that, say, c(x)  c(y); that is c(R~) + c(R~)  c(R~) + c(R~)  c(R~) + c(R~). But then c(R~)  c(R~), a contradiction. Thus G is 3edge colorable (the colors being taken from F  {e}). [7
F i g u r e 82. 84. O t h e r M a p  C o l o r i n g P r o b l e m s " The Heawood MapColoring Theorem Now let us consider other subspaces of IRa in which to pose mapcoloring questions such as that above, for the sphere (and plane).
84. THE HEAWOOD MAPCOLORING THEOREM
93
I21 ! ,
,
1
F i g u r e 83. Strangely enough, if we allow 3dimensional countries, arbitrarily many colors may be needed to color the map. This is indicated by Figure 83, in which the countries are numbered; it is seen that each country meets each of the other countries. (In general, n modified rectangular parallelepipeds are laid across n other such solids.) Perhaps it seems natural, since the coloring problem is apparently extraordinarily difficult for the sphere, and admits no finite answer in I~3, to consider next the surfaces Sk as candidates for maps and the corresponding mapcoloring questions. The Heawood Map Coloring Theorem (formerly the Heawood MapColoring Conjecture) has a particularly colorful background, as outlined in Chapter 1; also see J.W.T. Youngs [Y2]. We state the theorem first for the orientable case: T h m . 88. x ( S k ) 
[T+Vq+4SkJ2 , f o r k > O .
Note what happens if we replace k with 0 in this formula. This led many mathematicians to feel that the four color conjecture was probably true, and they were vindicated! Thus we can now take k >_ 0 in Theorem 88. The corresponding mapcoloring question can also be asked for the closed nonorientable surfaces Nk (spheres with k crosscaps). In 1959 Ringel [R10] showed the following (the case k = 2 was solved by Franklin [F4]): T h m . 89.
x(Nk)= [ 7 + ~ ]
, for k 
1 and k _> 3; x(N2) 6.
For example, the formula gives x(N~)  6 (for the projective plane). Figure 84 shows K6 imbedded in N~, indicating that x(N1) _ x(K6) 6. Recalling that the euler characteristics for Sk and Nk are given by n = 2  2k and n = 2  k respectively, we can combine Theorems 85, 88, and 89 as follows:
94
8. M A P  C O L O R I N G P R O B L E M S b
c
d
c
d
c Figure
b 84.
T h m . 810. Let M , be a closed 2manifold, other than the klein bottle, of characteristic n; then x(M,) = [ 7 +
v/49" 224nJ
For ease of notation, we let f(n) = 7+vqg24n 9We will now establish 2 what Heawood knew in 1890:
~(M~) ~ Lf(n)J. We proceed by a series of steps, following the translator's notes in Fr~chet and Fan [FF1]. L e m m a 811. Let a graph G, with p > 3, be 2cell imbedded in M~, with a denoting the average degree of the vertices of G. Then a < 6 ( 1  ~). PROOF. Note that a  p 9N o w 3 r _ 2 q  a p . Hence q _< 3 ( q  r)  3 ( p  n), so that
2qp (
a<6
_
1 
Also, p  q + r = n .
.
[I T h m . 812. x(N~) <_6. PROOF. We use induction on p, the order of a graph imbedded in N1. The result is clearly true for p < 6. Assume x(G) <_ 6 for all graphs in N1 with p  1 vertices, p > 7; let G be a graph imbedded in N1, with p vertices. If the imbedding is not 2cell, then (see Youngs [Y1]) "~(G)  0, and x(G) < 5. Otherwise, by Lemma 811, a < 6, so
84. THE HEAWOOD MAPCOLORING T H E O R E M
95
This Page that G hasIntentionally a vertex vLeft suchBlank that d(v) <_ 5. Then G  v is imbedded in NI, and x ( G  v) < 6, by the induction hypothesis. Since there are vertices of at most five colors adjacent to v, the sixth color can be used for v, and x(G) < 6. 13
Note that Theorem 812, together with Figure 84, show that x(N,) = 6 . The reader should locate the spot where the following argument fails for the sphere (and the projective plane as well; this is why these two surfaces are treated separately).
Thm. 813. X(Mn) _< Lf(n)J, for n # 2. PROOF. Thanks to Theorem 812, we may assume that n _< 0. We use induction on p, to show that x(G) _ [f(n)J, if G is imbedded in M,. (We may assume G to be connected, as the chromatic number of a graph is the largest chromatic number for its components.) It is clear that x(G) <_ [f(n)J if p < [f(n)J. Now assume that x(G) <_ [f(n)J for all graphs with fewer than p vertices and imbeddable in M,. Now, from the definition of f(n), we see that f 2 ( u )  7f(n) + 6n = 0; i.e. 6 (1  /  ~ , ) )  f(n)  1. If the imbedding of G (of order p > [f(n)J) in M , is 2cell, then Lemma 811 applies, and a<6
(n) (n) 1p
<6 1
f(n)
 f ( n ) 
1.
If the imbedding is not 2cell, then it is not minimal (see again Youngs [Y1]), and we can find a 2cell imbedding in Mm, where m > n. We then apply Lemma 811 as above, to get a <_ f ( m )  1 < f ( n )  1. Thus in either case a < f ( n )  1, and we can find a vertex v of G having d(v) <_ [f(n)J  1, so that (using x ( G  v) _< [f(n)J), x(G) <_ [f(n)J. This completes the proof. Cl The task remains to show that x(M~) _ [f(n)J, for M~ :~ N2, the klein bottle. This is done by finding a graph G imbeddable in M~ and having x(G) = Lf(n)J. For M2 = So,/s is such a graph; for M1 = N1, take G = / ( 6 (as in Figure 84); for M0 = SI, pick G = K7 (see Figure 85 for the dual of K~ in $1); for M2 = $2, let G = Ks. In fact, for M~ ~ N2, [f(n)J is attained by the largest complete graph imbeddable in M~. We now confine our attention to the orientable case and explore this claim in some detail.
96
8. M A P  C O L O R I N G P R O B L E M S
6
6 r
F i g u r e 85. Let us assume the truth of the Complete Graph Theorem (which will be discussed in more detail in Chapter 9): 7 ( K i n ) = [ (m  3) (m  4)
, form>3._
From this it will follow that x(Mn) >_ [f(n)J (in the orientable case; the nonorientable case is handled similarly).
T h m . 814
X(Sk)> [ / ( 2  2k)] = [7+4,+4sk]
PROOF. Consider Sk. Define m = [ f ( 2  2k)J, and now consider also Sy(gm). Note that 7(Kin) <_ k, so that x(S.r(Km) ) < x(Sk). Now gm imbeds in S.r(gm). Clearly x(S.r(Km) ) > m = I f ( 2  2k)J, so that
x(&) >_ Lf ( 2  2k)].
I:3
Theorems 813 and 814 combine to prove Theorem 88, with the understanding that it remains to establish the formula for the genus of Kin. Before indicating how this is done (in the next chapter), we pause for some related results. 85. A R e l a t e d P r o b l e m We have seen that, for every closed 2manifold , the maximum chromatic number of an imbedded graph is taken on by a complete graph. We now show that the complete graphs play the same role with respect to maximizing the minimum degree of an imbedded graph, with the sphere and the klein bottle as the sole exceptions. T h m . 815. Let M~ be a closed 2manifold of characteristic n, and G a graph. If G has an imbedding in M~, then 5(G) _ g(n), where

{ l~+V'4924'~J
,
ifn <2
5, if n  2 . Furthermore, there exists a graph G, imbeddable in M~, such that 
85. A RELATED PROBLEM
97
PROOF. The theorem is known to be true for n = 2, as Lemma 519 and the icosahedral graph show. Suppose now that n < 2 and that G is a graph having p vertices and q edges, with 5(G) > g(n), and a 2cell imbedding in M~ (~ So). By standard arguments, 2q > 3r, and also 2q > p(g(n) + 1). We may assume that G is connected, since if the theorem is true for every component of G, it is also true for G. The euler formula applies, so that
n=pq+r 2 1, _< ( )q g(n) + 1 3 ~
5  g(n) )q. (3(g(n) + 1 We may assume that n _< 0, as the above inequality is clearly impossible for n = 1. But for n <_ O, g(n) _> 6, so that
3n(g(n) + 1) 9(n) 5 But since 5(G) > g(n), p > g(n)+ 2, and q_<
2q > (g(n) + 2)(g(n)+ 1). We note that
(g(n) + 2 ) ( g ( n )  5 ) = [ 9 + x / 4294n j 2 >
[5+
v/49224nJ
(7 + x/492  24n )(  7 + x/'2~i2 24n)
It now follows that q_
(g(rt) + 2)(g(n)+
1)
2 3n(g(n) + 1) 5 _q,
a contradiction. Hence 5(G) < g(n). Now suppose that G has a non 2cell imbedding in M~. By a result of Youngs [Y1], G has a 2cell imbedding in some M~,, where n < n'. From what we have shown above, 5(G) <_ g(n') < g(n). Ringel and Youngs have shown [RY1] (also, see Chapter 9) that the complete graph K[g(22k)]§ is imbeddable in Sk, for k < 1. Ringel [RI0] has shown that the complete graph K[g(2k)]+, is imbeddable in Nk, for all positive k except k  2. It remains to find a graph G
98
8. M A P  C O L O R I N G P R O B L E M S
imbeddable in N2 and having (~(G)  6 . We begin by considering two projective planes, P1 and P2, each with a complete graph K5 imbedded as indicated in Figure 86. Cut open disks D1 and D2 from the interiors of the fivesided regions of PI and P2, respectively. Let T be a cylinder disjoint from P1 and P2, with simple closed boundary curves C1 and C2. Identify C1 with the boundary of D1 and C2 with the boundary of D2. The result, (P~  D~)t2 T t3 ( P 2  D2), is a klein bottle (see Problem 87). The graph G is then constructed by adding the edges (i, i')(i, (i + 1)'), i = 1, 2, 3, 4, 5, (where the vertex 6' is the same as the vertex 1'). This completes the proof. [7
b
c
d
b e
a
s
d
cb
P1
P2
bc
d
Figure 86. We thus make the following observation. The sphere is the only closed orientable 2manifold for which the maximum minimum degree is not attained by a complete graph. In contrast, we have seen that for every closed 2manifold (whether orientable or nonorientable), including the sphere, the maximum chromatic number is attained by a complete graph. 86. A F o u r  C o l o r T h e o r e m for t h e Torus Thus far in this chapter we have been discussing, for a given closed 2manifold M, the chromatic number of arbitrary graphs that can be imbedded in M. In this section we impose a restriction on the girth of the graphs we are considering. Def. 816. The girth g(G) of a graph G is the length of a shortest cycle (if any)in G. Thus a graph G with cycles but no triangles has g(G) > 4; if G is a forest, we write g(G)  c~. The following theorem was shown by Grhtzsch [G10]: T h m . 817. If 7(G) = 0 and g(G) > 4, then x(G) <_ 3.
86. A FOURCOLOR THEOREM FOR THE TORUS
99
The graph G = C~ shows that equality can hold in Theorem 817. In this section we [KW2] find an upper bound for the chromatic number of toroidal graphs having no triangles, and show that this bound is best possible. We also consider toroidal graphs of arbitrary girth. Def. 818. A connected graph G is said to be nedgecritical (n > 2) if x ( G )  n but, for any edge x of G, x ( G  x)  n  1. The next theorem is due to Dirac [D4]. T h m . 819. If G is nedgecritical, n > 4, and if G ~= K~, then 2q >_ ( n  1)p + n  3. We are now able to find the analogue of GrStzsch's Theorem, for the torus. T h m . 820. If 7(G) < 1 and g(G) > 4, then x(G) _< 4. PROOF. Let x ( G )  n _> 5. We first assume that G is nedgecritical, and hence connected. Since g(G) > 4, G ~ K~. By Theorem 819, 2q > ( n  1)p + n  3. Now if 7(G) = 1, then by Corollary 615, 4p_2q>
(n1)p+n3;
thus n < 4. If "y(G)  0, then n < 3, by Theorem 817. In either case we have a contradiction, so that n < 4. Now suppose that G is not nedgecritical. Then G contains an nedgecritical subgraph H, and the argument above shows that x ( G ) x(H) = n _ 4. I1 The graph of Figure 87, constructed by Mycielsky [M8] as an example of a graph having no triangles and chromatic number four, also has genus one, so that the bound of Theorem 820 cannot be improved. The situation for the torus is almost completely analyzed in the next theorem. T h m . 821. If "y(G) _< 1 and g(G) = m, then
100
8. M A P  C O L O R I N G P R O B L E M S
v
F i g u r e 87.
x(G)<_
7,
if m = 3
4,
ifm4or5
3,
if m _>_6.
Moreover, all the bounds are sharp, except possibly for m = 5. PROOF. If m > 6, then each region in an imbedding for G has at least six edges in its boundary, so that 2q >_ 6r. As in the proof of Theorem 820, we may assume that 7(G) = 1 and that G is nedgecritical, where n  x(G). If n _< 4, then 2q >_ 3p + 1, by Theorem 819. Then, by Corollary 514,
Opq+r 2q 1 < 
3
q+~
q
1 3'
an obvious contradiction. Hence for 7(G) _< 1 and must have x(G) _< 3. This bound is best possible, as subdivision G of the Petersen graph (shown imbedded 88) can always be found, having g(G) = m(m > 5), x(G) = 3 .
g(G) _> 6, we an appropriate in $1 in Figure 7(G) = 1, and
F i g u r e 88. For m  4 or 5, it follows from Theorem 820 that x(G) _< 4. (Now, see Problem 89.) Figure 87 shows that equality can hold for m  4. For m  3, we refer to the Heawood MapColoring Theorem. D
88. k  D E G E N E R A T E G R A P H S
101
Gimbel and Thomassen [GT1] showed that x(G) <_ 3, if 7(G) _< 2 and g(G) >_ 6. 87. A N i n e  C o l o r T h e o r e m for t h e T o r u s a n d K l e i n B o t t l e The material in this section is due to Ringel JR19]. Def. 822. A graph G is said to be 1imbeddable in a surface S if G can be represented on S so that each edge is crossed over by at most one other edge. Def. 823. The 1chromatic number xI(S) is the largest x(G) such that G is 1imbeddable in S. T h m . 824. The 1chromatic numbers xI(Sk) and xl(Nh) are bounded above as shown: (i) X, (Sk) _< [ 9+~kv~4T~]2, for k _> 1 (ii) xI(Nh)< [9+~/32h§
for h > 1
T h m . 825. The following hold:
(i) ~ 1 ( S 1 ) = 9, (ii) X, (N2) = 9, (iii) x,(Ss3) = 41. The result (iii) above was obtained using a modified current graph (see Chapter 9, for a discussion of the theory of current graphs.) 88. k  d e g e n e r a t e G r a p h s Before getting to one focal point of this text, in the next chapter, we digress briefly. The generalization below of Theorem 810 might be of interest. A coloring number for graphs closely related to the chromatic number is the vertexarboricity (see [CKWl].) Def. 826. The vertex arboricity, a(G), of a graph G is the minimum number of subsets that V(G) can be partitioned into so that each subset induces an acyclic graph. Def. 827. The vertex arboricity of a surface Sk is the maximum vertexarboricity among all graphs which can be imbedded in Sk.
102
8. MAPCOLORING PROBLEMS
In 1969, Kronk [K3] showed that the vertex arboricity of Sk, k > 0, is ~9+,/1+48k]4. Chartrand and Kronk [CK2], also in 1969, proved that /
!
t
.I
the vertexarboricity of the sphere is three. The similarity of Kronk's result to those of Ringel and of Ringel and Youngs for the chromatic number suggested the generalization discussed below. Def. 828. A graph G is said to be kdegenerate if every induced subgraph H of G satisfies the inequality 5(H) <_ k. Def. 829. The vertex partition number, pk(G), of a graph G is the minimum number of subsets into which V(G) can be partitioned so that each subset induces a kdegenerate subgraph of G. The parameters po(G) and p~(G) are the chromatic number and vertex arboricity of G, respectively (see Problem 84). A general study of kdegenerate graphs has been begun in [LW2], where many of the wellknown results for the chromatic number and the vertexarboricity of a graph have been extended to the parameters pk(G), for all nonnegative integers k. Def. 830. The vertex partition number of the closed 2manifold Mn, denoted by pk(Mn), is the maximum vertex partition number pk(G) among all graphs G which can be imbedded in M~. The following theorem (for a complete proof, see [LW3]) almost completely generalizes the results of Kronk, Ringel, Ringel and Youngs and Haken mentioned above. T h i n . 831. The vertex partition numbers for a closed 2manifold Mn are given by the formula: p,,(M,,)

[
(2 k + 7 ) + v / 4 9  24n
2k+2
J
whcre k = 0, 1,2,3,... ; and n = 2, 1,0,  1 ,  2 , . .  , following cases:
except for the
(i) in the orientable case, pl(So) = 3, p3(So) = p4(So) = 2; and (ii) in the nonorientable case, p0(N2) = 6, pl (N2) = 3, p2(N2) = 2. We make the following comments about the proof of Theorem 831. Set f ( k , n )  L(2k+7)+~/4924~J2k+2 The proof is divided into three parts. .
89. COLORING GRAPHS ON PSEUDOSURFACES
103
(i) pk (AI~) _ f(k, n), for Mn r So (the proof breaks down for the sphere, reminding us how obstinate the four color problem was.) (ii) pk(Mn) >_ f(k,n), for M~ r N2 (the proof fails for the klein bottle). (iii) the exceptional cases are treated separately: (a) for M~ = So, p~ (So) = 3 appears in [CK2]; for pk(S0) = 2, k  2, 3, 4, see Problem 85; finally, pk(So) = 1 for k _ 5, since any planar graph is 5degenerate, by Lemma 519. (b) For M~  N2, additional ad hoc arguments are devised. For example, the graph constructed in Figure 86 shows that ph(N2) _ 2; from (i) we see that ph(N2) <_ 2; thus ps(N2)  2. The values of p~(N2) and p2(N2) were settled by Borodin [B13] in 1976.
89. C o l o r i n g G r a p h s on P s e u d o s u r f a c e s The pseudosurfaces S(k; n~ (m~),..., nt (mr)) have been defined in Section 55 and reencountered in Sections 67 and 69. Dewdney [D2] has studied a subclass of these pseudosurfaces, namely those of the form S(0, n(2)): Def. 832. The chromatic number, X(8(0; n(2))), of the pseudosurface S(0; n(2)) is the largest chromatic number x(G) of any graph G that can be imbedded in S(0; n(2)). T h m . 833. x(S(0; n(2))) < n + 4, for n > 0; equality holds for n 1,2,3,4. For example, Figure 67 shows/(5 imbedded in S(0; 1(2)), showing that x(S(0; 1(2)) >_ 5. Similarly, K6 imbeds in S(0; 2(2)), to give equality for the case n = 2. (See Problem 610.) Note that we state this coloring problem for graphs rather than for maps; the dual of G in S(0; n(2)) is not a 2cell imbedding, so that there is not the natural correspondence we find for surfaces. (The cases n = 3 and 4 were established by Mark O'Bryan and James Williamson respectively.) Then in 1974, Borodin and Melnikov IBM2] solved this particular problem completely, except for the case n  0 now covered by the Fourcolor Theorem; we state the complete solution:
104
8. MAPCOLORING PROBLEMS
T h m . 834.
X(S(0; n ( 2 ) ) )
n+4, 8, [7+V',+24n]2 ,
0<_n<_4, n  5, 6 <_ n <_ 12,
12,
n _ 12.
Thus we have the mapcoloring numbers for the sphere, where n countries have two components, and that twelve is the largest of all these numbers (see Problem 86). Heawood [H4] generalized to ask for the mapcoloring number x(S, c) for a surface S (orientable or nonorientable) of characteristic n, where each country has at most c components, and showed for every case but the sphere for c = 1 that this number is bounded above by: T h m . 835. 6c + 1 + v/(6c + 1) 2  24n /
x ( S , c ) <_
2
J
Note that the case c  1 is the one of primary interest (the Heawood Map Coloring Theorems), and that the bound does hold for c  1 and n = 2 as well (the Fourcolor Theorem.) Moreover, we have seen that X(So, 2) = 12. Recently it has been shown that equality also holds in Theorem 835, for certain other cases: T h m . 836. (Jackson and Ringel [JR2]
X(So, C) =
6c, for c > 2.
T h i n . 837. (Taylor [T1]) x(S1, c)  G c 
1, for c :> 1.
T h m . 838. (Jackson and Ringel [JR1]) x ( N 1 , c)  6c, for c > 1.
T h m . S39. (Jackson and Ringel [JR3], Borodin [B14]) Let g(c,n) =
6c + 1 + V/(6c + 1) 2  2 4 n [ . 2
J
811. P R O B L E M S
105
then x(S, c)  g(c, n), if:
(i) S  Nk and g(c, n)  1, 4, 7 (mod 12), unless k  2 and c   1. (ii) S  Sk, c is even, and g(c, n)  1 (mod 12). (iii) S  Sk, c is odd, and g(c, n)  4, 7 (mod 12). It remains to construct the "verification figures" (i.e. the appropriate pseudosurface imbeddings) for the cases not covered above. (See Problem 817.) 810. T h e C o c h r o m a t i c N u m b e r of Surfaces The material in this section is taken from Straight ([$25] and [S26].) Def. 840. The cochromatic number, z(G), of a graph G is the minimum number of subsets into which V(G) can be partitioned so that each subset induces either an empty or a complete subgraph of G. Def. 841. The cochromatic number, z(S), of a surface S, is the maximum z(G) such that G imbeds in S. T h m . 842. z(S~) < x(S~), with equality if and only if n = 0. For example, z(C5 U/(4)  4, so that Z(So)  4. T h i n . 843. For n _> 4, z(Nn) < x(Nn).
T h i n . 844. (i) (ii) (iii) (iv) (v)
Z(So) = 4 z(N~) = 5 z(N2) = 6 z(N3) = 6 z(N,) = 7.
Straight conjectures that, in general, z(S) is the maximum n such that U~=~K~ imbeds in S. 811. P r o b l e m s 81.) Let G ~ Kn; show that X(G)  2 if and only if G is bipartite. 82.) Find x(C~), for all cycles C~.
106
8. M A P  C O L O R I N G P R O B L E M S
83.) Find an imbedding of K7 on $1. Form the dual of this imbedding, and explain why this shows that x(S1) >_ 7. 84.) Show that po(G)  ~((G) and that pl (G)  a(G). 85.) Show that pk(So)  2, for k  2,3, 4. (Hint: for each k, use induction to show that pk(So) _< 2. Then consider graphs of certain regular polyhedra.) 86.) *Show (as Ringel and Heawood did) that any map on the surface of the sphere, in which each country has at most two components, can be colored with 12 colors. (Hint: it may be helpful to show that if a graph G is ncritical, then 5(G) >_ n  1; i.e. if ~((G)  n, but ~((Gv)  n  1 , for all vertices v in G. Then form two "dual" graphs for an arbitrary map, one where the vertices represent countries, the other with vertices representing regions of land. Use also the fact that q __ 3 p  6, for planar connected graphs.) Interpret this result for pseudosurfaces. Compare Problem 612. 87.) Show that the connected sum of two projective planes (as in the proof of Theorem 815) is a klein bottle. (Hint" find the characteristic of the resulting closed 2manifold, using the graph G constructed in the same proof.) 88.) Show that x(G) = 4, for the graph G of Figure 87. 89.) **Does there exist a toroidal graph G having g(G)  5 and ~((a)

47
810.) *Prove or disprove" /(9 imbeds in S(0;5(2)) (and hence x(S(0; 5(2))  9.) Is ~((S(0;n(2)))  n + 4 for all n? Compare Problems 612 and 86. Does K,0 imbed in S(0; 7(2))? 811.) Define the chromatic number of a group to be" x(F) = mina x(Ga(F)) (cf Babai [B1]). Find x(F), for F  Z~, Z2 • Z~, (Z2) ~, D~,Z2 • D~, S~. Show x(F) __ 3, for F finite abelian or F  A~. 812.) *If F has a normal subgroup F,, show that ~((F) _< X(F/F1). Thus if F is solvable (note that this includes all odd order groups), then ~((F) <_ 3. If F has a subgroup of index 2, then show that x(F) _< 2. 813.) Show that x(F)  2 if and only if F has a subgroup of index 2. Conclude that x(A,)  3, for n _> 3. 814.) **Is x(F) _< 3 for all groups F'? 815.) Is x(Fx) _ x(F2), if F~ _ F2? 816.) Extend the definition of x(F) to pk(F), for arbitrary vertex partition numbers. Study this family of parameters. 817.) **Find the imbeddings called for at the conclusion of Section 89. 818.) **Study the conjecture given at the conclusion of Section 810. 819.) Show that, for any integer pair (k, n), when k > 0 and 3 <_ n < )(.(St=), these exists a triangulation of Sk by a graph G having x ( G )  n. (Harary, Korzhik, Lawrencenko [HKL1]).