Map-Coloring Problems

Map-Coloring Problems

CHAPTER 8 MAP-COLORING PROBLEMS In this chapter we will see that the famous four-color theorem can be formulated - and studied - in graph-theoretic...

756KB Sizes 0 Downloads 7 Views

Recommend Documents

Problems
This chapter presents a series of ancient problems, followed by various extremal problems in algebra and geometry. These

Problems
This chapter presents the problems relevant to the topic of the working conference, Decision Problems in Algebra. For ex

SPOILAGE PROBLEMS | Problems Caused by Bacteria
Spoilage of food can be described as a loss of its qualitative properties with regard to color, flavor, texture, odor, o

CHAPTER 8

MAP-COLORING

PROBLEMS

In this chapter we will see that the famous four-color theorem can be formulated - and studied - in graph-theoretical terms. Graph theory will be used to establish the five-color 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 8-6 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 four-color 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. 8-1. 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. 8-1. 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. 8-2. 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 five-color theorem of the next section are subsumed by the Four-Color Theorem. But we want to include the proofs, as the techniques they illustrate will have value later. T h m . 8-3. 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 6-colorable. Let G be planar, of order p. By Lemma 5-19, 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 8-2. 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].

8-3. THE FOUR-COLOR T H E O R E M

91

T h m . 8-4. 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 5-colorable. Let G be planar, with p vertices. By L e m m a 5-19, G contains a vertex v of degree 5 or less. By the induction hypothesis, x ( G - v) < 5; denote the colors in a 5-coloring 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 8-1, and that v~ is colored with color i. Consider now any two colors assigned to non-consecutive 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 5-coloring 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 8-1. 8-3. T h e F o u r - C o l o r T h e o r e m In the notation of Section 8-1, the Four-color Theorem becomes: T h m . 8-5.

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 8-5 are enormously more complicated than those of either Theorem 8-3 or 8-4, in part due to the positive difference upon subtracting the number of colors, four, from

92

8. MAP-COLORING 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 2-manifold for which the maximum minimum degree is not obtained by a complete graph. (See Theorem 8-15.) The sphere is also the only closed orientable 2manifold of positive characteristic. This is why Theorem 8-13 does not contain a (simple) proof of the Four-Color Theorem. There are many equivalent formulations of the Four-color 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. 8-6. A graph G is said to be n-edge colorable if n colors can be assigned to E(G) so that adjacent edges are colored differently. T h m . 8-7. Every cubic plane block is 3-edge colorable. PROOF. Let G be a cubic plane block. By Theorem 8-5, 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 8-2. 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 3-edge colorable (the colors being taken from F - {e}). [-7

F i g u r e 8-2. 8-4. 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 Map-Coloring Theorem Now let us consider other subspaces of IRa in which to pose mapcoloring questions such as that above, for the sphere (and plane).

8-4. THE HEAWOOD MAP-COLORING THEOREM

93

I21 ! ,

,

1

F i g u r e 8-3. Strangely enough, if we allow 3-dimensional countries, arbitrarily many colors may be needed to color the map. This is indicated by Figure 8-3, 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 map-coloring 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 . 8-8. 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 8-8. The corresponding map-coloring question can also be asked for the closed non-orientable surfaces Nk (spheres with k cross-caps). In 1959 Ringel [R10] showed the following (the case k = 2 was solved by Franklin [F4]): T h m . 8-9.

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 8-4 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 8-5, 8-8, and 8-9 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 8-4.

T h m . 8-10. Let M , be a closed 2-manifold, other than the klein bottle, of characteristic n; then x(M,) = [ 7 +

v/49" 224nJ

For ease of notation, we let f(n) = 7+vqg-24n 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 8-11. Let a graph G, with p > 3, be 2-cell 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 . 8-12. 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 2-cell, then (see Youngs [Y1]) "~(G) - 0, and x(G) < 5. Otherwise, by Lemma 8-11, a < 6, so

8-4. THE HEAWOOD MAP-COLORING 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. 1-3

Note that Theorem 8-12, together with Figure 8-4, 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. 8-13. X(Mn) _< Lf(n)J, for n # 2. PROOF. Thanks to Theorem 8-12, 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 2-cell, then Lemma 8-11 applies, and a<6

(n) (n) 1-p

<6 1

f(n)

-- f ( n ) -

1.

If the imbedding is not 2-cell, then it is not minimal (see again Youngs [Y1]), and we can find a 2-cell imbedding in Mm, where m > n. We then apply Lemma 8-11 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 8-4); for M0 = SI, pick G = K7 (see Figure 8-5 for the dual of K~ in $1); for M-2 = $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 8-5. 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 non-orientable case is handled similarly).

T h m . 8-14

X(Sk)> [ / ( 2 - 2k)] = [7+4,+4sk]

PROOF. Consider Sk. Define m = [ f ( 2 - 2k)J, and now consider also S-y(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 8-13 and 8-14 combine to prove Theorem 8-8, 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. 8-5. A R e l a t e d P r o b l e m We have seen that, for every closed 2-manifold , 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 . 8-15. Let M~ be a closed 2-manifold of characteristic n, and G a graph. If G has an imbedding in M~, then 5(G) _ g(n), where

-

{ l~+V'49-24'~J

,

ifn <2

5, if n - 2 . Furthermore, there exists a graph G, imbeddable in M~, such that -

8-5. A RELATED PROBLEM

97

PROOF. The theorem is known to be true for n = 2, as Lemma 5-19 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 2-cell 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=p-q+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 / 4294-n 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 2-cell imbedding in M~. By a result of Youngs [Y1], G has a 2-cell 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(2-2k)]§ is imbeddable in Sk, for k < 1. Ringel [RI0] has shown that the complete graph K[g(2-k)]+, 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 8-6. Cut open disks D1 and D2 from the interiors of the five-sided 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 8-7). 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 8-6. We thus make the following observation. The sphere is the only closed orientable 2-manifold for which the maximum minimum degree is not attained by a complete graph. In contrast, we have seen that for every closed 2-manifold (whether orientable or non-orientable), including the sphere, the maximum chromatic number is attained by a complete graph. 8-6. 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 2-manifold 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. 8-16. 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 . 8-17. If 7(G) = 0 and g(G) > 4, then x(G) <_ 3.

8-6. A FOUR-COLOR THEOREM FOR THE TORUS

99

The graph G = C~ shows that equality can hold in Theorem 8-17. 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. 8-18. A connected graph G is said to be n-edge-critical (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 . 8-19. If G is n-edge-critical, 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 . 8-20. If 7(G) < 1 and g(G) > 4, then x(G) _< 4. PROOF. Let x ( G ) - n _> 5. We first assume that G is n-edgecritical, and hence connected. Since g(G) > 4, G ~ K~. By Theorem 8-19, 2q > ( n - 1)p + n - 3. Now if 7(G) = 1, then by Corollary 6-15, 4p_2q>

(n-1)p+n-3;

thus n < 4. If "y(G) - 0, then n < 3, by Theorem 8-17. In either case we have a contradiction, so that n < 4. Now suppose that G is not n-edge-critical. Then G contains an nedge-critical subgraph H, and the argument above shows that x ( G ) x(H) = n _ 4. I1 The graph of Figure 8-7, 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 8-20 cannot be improved. The situation for the torus is almost completely analyzed in the next theorem. T h m . 8-21. 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 8-7.

x(G)<_

7,

if m = 3

4,

ifm-4or5

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 8-20, we may assume that 7(G) = 1 and that G is n-edgecritical, where n - x(G). If n _< 4, then 2q >_ 3p + 1, by Theorem 8-19. Then, by Corollary 5-14,

O-p-q+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 8-8) 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 8-8. For m - 4 or 5, it follows from Theorem 8-20 that x(G) _< 4. (Now, see Problem 8-9.) Figure 8-7 shows that equality can hold for m - 4. For m - 3, we refer to the Heawood Map-Coloring Theorem. D

8-8. 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. 8-7. 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. 8-22. A graph G is said to be 1-imbeddable 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. 8-23. The 1-chromatic number xI(S) is the largest x(G) such that G is 1-imbeddable in S. T h m . 8-24. The 1-chromatic 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 . 8-25. 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.) 8-8. 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 8-10 might be of interest. A coloring number for graphs closely related to the chromatic number is the vertex-arboricity (see [CKWl].) Def. 8-26. 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. 8-27. The vertex arboricity of a surface Sk is the maximum vertex-arboricity among all graphs which can be imbedded in Sk.

102

8. MAP-COLORING 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 vertex-arboricity 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. 8-28. A graph G is said to be k-degenerate if every induced subgraph H of G satisfies the inequality 5(H) <_ k. Def. 8-29. 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 k-degenerate subgraph of G. The parameters po(G) and p~(G) are the chromatic number and vertex arboricity of G, respectively (see Problem 8-4). A general study of k-degenerate graphs has been begun in [LW2], where many of the well-known results for the chromatic number and the vertex-arboricity of a graph have been extended to the parameters pk(G), for all nonnegative integers k. Def. 8-30. The vertex partition number of the closed 2-manifold 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 . 8-31. The vertex partition numbers for a closed 2-manifold 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 non-orientable case, p0(N2) = 6, pl (N2) = 3, p2(N2) = 2. We make the following comments about the proof of Theorem 8-31. Set f ( k , n ) - L(2k+7)+~/49-24~J2k+2 The proof is divided into three parts. .

8-9. 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 8-5; finally, pk(So) = 1 for k _ 5, since any planar graph is 5-degenerate, by Lemma 5-19. (b) For M~ - N2, additional ad hoc arguments are devised. For example, the graph constructed in Figure 8-6 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.

8-9. 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 5-5 and re-encountered in Sections 6-7 and 6-9. Dewdney [D2] has studied a subclass of these pseudosurfaces, namely those of the form S(0, n(2)): Def. 8-32. 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 . 8-33. x(S(0; n(2))) < n + 4, for n > 0; equality holds for n 1,2,3,4. For example, Figure 6-7 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 6-10.) 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 2-cell 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 Four-color Theorem; we state the complete solution:

104

8. MAP-COLORING PROBLEMS

T h m . 8-34.

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 map-coloring numbers for the sphere, where n countries have two components, and that twelve is the largest of all these numbers (see Problem 8-6). Heawood [H4] generalized to ask for the map-coloring 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 . 8-35. 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 Four-color Theorem.) Moreover, we have seen that X(So, 2) = 12. Recently it has been shown that equality also holds in Theorem 8-35, for certain other cases: T h m . 8-36. (Jackson and Ringel [JR2]

X(So, C) =

6c, for c > 2.

T h i n . 8-37. (Taylor [T1]) x(S1, c) - G c -

1, for c :> 1.

T h m . 8-38. (Jackson and Ringel [JR1]) x ( N 1 , c) - 6c, for c > 1.

T h m . S-39. (Jackson and Ringel [JR3], Borodin [B14]) Let g(c,n) =

6c + 1 + V/(6c + 1) 2 - 2 4 n [ . 2

J

8-11. 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 8-17.) 8-10. 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. 8-40. 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. 8-41. The cochromatic number, z(S), of a surface S, is the maximum z(G) such that G imbeds in S. T h m . 8-42. 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 . 8-43. For n _> 4, z(Nn) < x(Nn).

T h i n . 8-44. (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. 8-11. P r o b l e m s 8-1.) Let G ~ Kn; show that X(G) - 2 if and only if G is bipartite. 8-2.) 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

8-3.) Find an imbedding of K7 on $1. Form the dual of this imbedding, and explain why this shows that x(S1) >_ 7. 8-4.) Show that po(G) - ~((G) and that pl (G) - a(G). 8-5.) 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.) 8-6.) *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 n-critical, then 5(G) >_ n - 1; i.e. if ~((G) - n, but ~((G-v) - 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 pseudo-surfaces. Compare Problem 6-12. 8-7.) Show that the connected sum of two projective planes (as in the proof of Theorem 8-15) is a klein bottle. (Hint" find the characteristic of the resulting closed 2-manifold, using the graph G constructed in the same proof.) 8-8.) Show that x(G) = 4, for the graph G of Figure 8-7. 8-9.) **Does there exist a toroidal graph G having g(G) - 5 and ~((a)

-

47

8-10.) *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 6-12 and 8-6. Does K,0 imbed in S(0; 7(2))? 8-11.) 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~. 8-12.) *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. 8-13.) Show that x(F) - 2 if and only if F has a subgroup of index 2. Conclude that x(A,) - 3, for n _> 3. 8-14.) **Is x(F) _< 3 for all groups F'? 8-15.) Is x(Fx) _ x(F2), if F~ _ F2? 8-16.) Extend the definition of x(F) to pk(F), for arbitrary vertex partition numbers. Study this family of parameters. 8-17.) **Find the imbeddings called for at the conclusion of Section 8-9. 8-18.) **Study the conjecture given at the conclusion of Section 8-10. 8-19.) 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]).