3-Colorability of plane hypergraphs

3-COLORABILITY OF PLANE HYPERGRAPHS S. G. Indzheyan

UDC 519. i

In this paper, we present sufficient conditions for 3-colorability of planar hypergraphs. Colorability in the sense of Erdos-Hajnal is considered. For the main definitions, see [I]. The problem 3-COLORABILITY OF A PLANAR GRAPH is NP-complete [2]. The problem of 3colorability of a planar hypergraph is obviously no less difficult, and it is natural to try and find at least some sufficient conditions. Let X = { ~ , xs.....xp} be a set and E a family of subsets from X. called a hypergraph with vertex set X and edge set E, w h e r e X = e ~ f.

The pair H = (X, E) is We assume that for any

e6E, le]~2. An ordinary graph is a particular case of the hypergraph H = (X, E) such that for each edge e 6 E we have lel = 2. Note that this definition of a graph coincides with Harary's definition of multigraph [3]. With each hypergraph H is associated its Koenig representation K(H) with the vertex set X U E and edge set {(x, e) E X x E/x6~. H is a planar hypergraph if its Koenig representation is planar graph. This means that a planar hypergraph may be fitted on a plane (or on a sphere) so that each vertex corresponds to a point and each edge e to a region which contains all the incident vertices (and only they) in the plane (the sphere). If ei~=es ~i, es6 E), then the regions corresponding to the edges e I and e 2 intersect only at the points corresponding to the common incident vertices. An edge of the hypergraph H is called an edge of degree i if lel = i. By H' we denote the graph made up of the edges of degree 2 of the hypergraph H and its incident vertices by m1(H) the number of edges of degree i of the hypergraph H, by m(H) the number of edges of H, and by n I = n1(G) the number of vertices of degree i of the graph G. Let s(G) be the maximum degree of the vertices of the graph G, 9(x) the degree of the vertex x. Definition. The planar graph G = (X, U) without 2-faces and with some labeled edges is called (n; t)-quasicolorable if its vertices may be colored in n colors so that the ends of the labeled edges have different colors and each face contains at least two differently colored vertices, with the possible exception of those faces r for which X(F) N X n ~ = ~ and

IX (r) l < t. Here X(F) is the set of vertices on the border of the face r, X~ = X(G~) is the set of vertices incident on the labeled edges, G~ = (XH, U~) is the graph generated by the labeled edges of G and their incident vertices, IX(F)I is the number of elements in the set X(F). Let W k be the class of planar graphs with the following property: any planar hypergraph H is 3-colorable if H'6Wk and for any edge e, lel~k. Clearly, W s _ W 4 ~ W ~ . . . ~ W h . Note that the class W defined in [4] coincides with W a. A conjecture advanced in [4] suggests that if G is a planar graph such that m (O)~.<8 and G contains no complete four-vertex K~, then G 6W~. It is easily seen (this is clear from the definition of planar hypergraph) that in order to prove this conjecture, it suffices to prove the theorem of planar triangulations (recall that a triangulation is a planar graph whose faces are simple cycles of length 3; multiple edges are allowed, on condition that no pair of such form the border of some face). We know that for any planar graph

5ni + 4n2+ 3n8 + 2n4+ns~>12.

(1)

THEOREM i. Each planar triangulation with at most 8 labeled edges which do not form a complete four-vertex K~ is (3; 3)-colorable. Translated from Kibernetika, No. 2, pp. 10-15, March-April, 1987. mitted March Ii, 1985.

158

0011-4235/87/2302-0158512.50

Original article sub-

9 1987 Plenum Publishing Corporation

Proof. Assume that this is not so and let G = (X, U) be a triangulation with the smallest number of vertices which satisfies the conditions of the theorem and is not (3; 3)colorable. Clearly, G contains no vertices of degree <3. Let us prove some propositions about this triangulation. Proposition i~ labeled.

If the vertex x 6 G

Js of degree 3, then all its incident edges are

Proof. Let x 6 G be a vertex of degree 3, (x, xl), (x, x2), (x, xs) its incident edges, and the edge (x, x I) is not labeled. Consider the triangulation G - x obtained by removing the vertex x from G. Since G - x has one vertex less than G, it is (3; 3)-quasicolorab!e. Having colored the vertices of G - x, restore G and color x in a color which is different from the colors of x2, x 3. The result is obviously a (3~ 3)-quasicoioring for G. The contradiction proves Proposition i. Pr_Ep~osition 2.

"3 (G) < 3.

Proof. Assume that ns(G) > 3. If no two vertices of degree 3 have a common edges then there are no fewer than 9 labeled edges in the triangulation G, a contradiction~ At the sane times no three vertices of degree 3 may have pairwise common labeled edges, since the labeled edges do not form a complete four-vertex. This means that already for n~(G) = 4 the number of labeled edges is at least I0~ a contradiction. Proposition 3. If the vertex x 6 G is of degree 4, then at least two of its incident edges are labeled, and if precisely two incident edges are labeled, then they are on the border of the same face. Proof. Assume that for the vertex x 6 G we have p(x) = 4, and among the edges (x, xl), (x, x2) , (x, xs), (x, x~) only (x, x l) is labeled. Consider the triangulation G ~ obtained from G be removing the vertex x and adding an unlabeled edge (x 2, x~). Clearly, G' is a triangulation with one vertex less than G. (3; 3)-quasicolorable.

Therefore, the graph G ~ is

Color G' in the colors % 6, and 7. Let the vertex x I be colored ~. If the vertex x in G cannot be colored 6, this means that either the vertices x~, x a or the vertices x a, x~ are colored ~. Then color the vertex x using >. The result is obviously a (3; 3)-quasicoloring for G. Now assume that precisely two edges are labeled, (x, x~) and (x, x~), and they are not on the border of the same face. Consider the triangulation G' obtained from G by removing the vertex x and adding an unlabeled edge (x2, x 4). Since G' has one vertex fewer than c~, it is (3; 3)-quasicolorable. Color G' using ~, ~, and ~. If the vertices xl and x 3 have the same color, e say, then restoring G we color the vertex x in ~. If x i and x 3 are differently colored ~ and 8, respectivelys then restoring G we color the vertex x using y~ The result is clearly a (3; 3)-quasicoloring of G. Q.E.D. Proposition 4. Let the vertex x 6 G of degree 4 be incident on the edges \ x2), (x, xs) ~ (x, x4). If the last two edges are unlabeled, then the edge ( x ~ x 4) is not labeled either and belongs to some subgraph K~ in which all the other edges are labeled. Proof______~.Assume that, among the edges incident on the vertex x 6 G of degree 4, the edges (x, x s) and (x, x~) are unlabeled [so that the edges (x, x l) and (x, x=) are necessarily labeled], and the edge (x 3, xu) is labeled. Consider the triangulation G' obtained from G by removing the vertex x and adding the edge (x=, x~). Since G' contains one vertex fewer than G and the labeled edges in G' do not form a complete four-vertex, it is (3; 3),quasicolorableo Color the vertices of G' in ~, ~, and 7. If the vertices x I and x= are colored and 8, respectively, then restoring G, color x in 7. If x~ and x 2 have the same color, then x in the restored graph is colored in one of the remaining colors. The result is obviously a (3; 3)-quasicoloring for G. Thus, the edge (x~, x 4) may not be labeled. We will show that it belongs to some subgraph K~ in which all the other edges are labeled. Assume that this is not so. Consider the triangulation G ~ obtained from G by removing the vertex x and adding an unlabeled edge (x2, x~). Let (x~, x~) be a labeled edge in G ~ The graph G' contains one vertex fewer than G, the number of labeled edges in G' is at most 7 [since with the vertex x we removed two labeled edges and added only one, (x~, x~)~, and

159

:

l

Fig. 1

Fig. 2

Fig. 3

the labeled edges do not form a complete four-vertex, since G did not contain a complete four-vertex with the edge (x s, xw) and all the other edges labeled. Thus, G' is (3; 3)quasicolorable. Having colored G', restore G leaving the colors of all the vertices unchanged and color x a different color from that of x I and x 2. The result is obviously a (3; 3)-quasicoloring for G. QED. Proposition 5. edges are labeled.

If the vertex x 6 G is of degree 5, then at least two of its incident

Proof. Assume the contrary. Let the vertex x of degree 5 be incident on the edges (x, xl), ~ , x2), (x, x3), (x, x~), and (x, x s) among which only (x, x I) is labeled (Fig. i). If at least one of the edges (x 2, x3), (xw, x s) does not belong to some subgraph K 4 in which all the other edges are labeled, we have an obvious contradiction. Indeed, let (x2, x~) be such an edge. Consider the triangulation G' obtained from G be removing the vertex x and adding the edges (x I, xw) and (xz, x~) is already labeled. Since (x2~ xs) in G does not belong to any subgraph K 4 with all the other edges labeled, then G' contains no complete fourvertex with all edges labeled. At the same time, the number of labeled edges in G' is at most 8, since we removed one labeled edge (x, x I) and added another labeled edge (x2, x3). Since the graph G' satisfies the conditions of the theorem and contains one vertex fewer than G, it is (3; 3)-quasicolorable. Color the vertices of G' in =, 8, and y. Let x I be colored =. If the vertex x in G cannot be colored B, this means that either x3, x 4 or x4, x s are colored 6. Then color the vertex x using y. The result is obviously a (3; 3)-quasicoloring for G, a contradiction. Therefore, the edges (x2, x3), (xw, x s) also belong to some subgraph K4 with all the other edges labeled. But this is impossible, since these two subgraphs K 4 can have no common edges, which implies that the number of labeled edges in G is greater than 8. The contradiction proves Proposition 5. Proposition 6. edges labeled.

There is at most one vertex x 6 G of degree 4 with only two incident

Proof. Assume the contrary. Let the vertices x and y be of degree 4. The vertex x (respectively, y) is incident on the edges (x, xl), (x, x2), (x, x~), (x, x4) [respectively, (Y, Yl), (Y, Y2), (Y, Y3), (Y, Yw)], of which only the first two are labeled. By Proposition 4, x and y have a common labeled edge. Indeed, assume that y ~ x i, where i6 [|, 2]. Since only two labeled edges are incident on the vertex x, then by Proposition 4 the edge (x~, xw) should be included in some subgraph K 4 with all the other edges labeled. But at the same time y does not coincide with any of the vertices of the subgraph Kw, which means that no fewer than 9 edges are labeled in G (two of them are incident on x, five are incident on the vertices of Kw, and two more on y), a contradiction. Thus, we have either y = x I or y = x 2. Without loss of generality, let y = x 2. Similar argument shows that x I = Yl where i6 [8, 4] (Fig. 2), which implies that p(x~) > 5. It is easy to see that p(x 3) > 5 since p(xs) = 5 would immediately imply the existence of the edge (x 2, z2), contradicting the equality p(y) = 4. Moreover, p(x I) > 5, since p(x I) ~ 3 and G has no vertices of degree 2. But by inequality (i) there should exist at least one vertex of degree ~ b which is distinct from all the vertices of Fig. 2, whence it follows that more than 8 edges are labeled in G. The contradiction proves Proposition 6.

160

Let m' = m'(G) be the number of labeled edges in the triangulation G. tions i-6~

2m'

- ~f3ns+3n 4 - 1 + 2 n ~ , [3n.~ + 2n~,

R e c a l l t h a t n1(G) = n2(G) = 0 and ns ( G ) < 3.

Then by Proposi-

n4 > 0 , n, = 0.

Consider the f o l l o w i n g four c a s e s ~

Case 1: n3= 0. Then t h e i n e q u a l i t y (1) becomes 2n4+ns~12, and 2m'~3n4--'l+_2_n~ Since m'~8, t h e n l f ~ 2 m ' ~ 3 n , - - I +2n5. Moreover, n 4 ~ f - - n j 2 and we get 1 6 j > 2 m ' ~ 3 n ~ . i +2n.~ ~ 3 ( 6 - - n~[2)~--l+2h~i7 + ha~2>~ 17, since n~/2 is a nonnegative number. The contradiction rules out Case I. Case 2: n a = i. Then the inequality (i) becomes 2n4-~-n~9~ and 2 n ! ~ 3 - k S n 4 - | ~-2n5, Hence 16 ~ 2m" ~ 3n4 ~- 2 q- 2n~. At the same time n ~ 4.5 -- n~/2 and 16 ~ 15.5 ~u rtj2. Prom the last inequality we get ns,~< I. Clearly n s ~ 0, since for n s = 0 and n3 = i we would get from (i) 2 n 4 ~ 9 whence n 4 ~ 5 (since n~ is an integer). But then 2 m ~ |7, whence m ' ~ 9 (since m' is an integer), a contradiction. It thus remains to consider the system of values n s=

1; n 4t>4;

n s = 1.

Let the vertex x 6 G be of degree 3 (Pig. 3)~ If none of the vertices of degree ~ 5 coin~ cides with any of the vertices x~, x ~ or x s, we obtain that the graph G, in addition to the edges (x, x~), (x, x2), (x, xs), should have at least (3n~ - i + 2ns)/2 labeled edges, i.e., m ' i > 3 + (3.4-- |q- 2 ) / 2 > 8 , a contradiction. If only one of the vertices x~, x2, xs is of d e g r e e ~ 5 , then, in addition to these three labeled edges, there should be at least (3n~ - I + 2n s - 1)/2 labeled edges, i.e., m' i> 3 + (3.4 -- ] -? 2 -- I)/2 = 9, again a contradiction. Thus~ at ].east two vertices of degree ~ 5 should coincide with x ~ x=, xa, and so at least one of these three vertices should be of degree 4 (since n s = i). Let x~ be this vertex, and let y be the fourth vertex adjacent to x~ (Pig. 4). But then either p (x~)~ ~, or p (xs)~>6, since by Proposition 4 either (y, x s) or (y, x 2) belong to some subgraph K+ with all the other edges labeled. Thus, at most two vertices of degree ~ 5 may have a conm~on labeled edge with vertex x, which means that at least (3n~ - I + 2n s - 2)/2 additional edges should be labeled, i.e., m ' ~ > 3 + ( 3 . 4 - - ! nu 2 - 2 ) / 2 > 8 . The contradiction rules out Case 2. Case 3: n~ = 2. Then the inequality (1) becomes 2~, + ~ ~ 6, whence ~ ~ 3--~/2o At the same time, 16 I> 2m' ~> 3a~ + 3n, -- I + 2n~ i.e., 16 ~> 6 + 3n~ -- l + 2n~I> 6 + 3 (3 -- nJ2) + 29~ -i ! = 14 q- ha~2. Hence it follows that n 5 ~ . 4 and n 4 ~ |. Since n ~ 0 and | 6 ~ 3 n ~ / - 3a~ -- I + 2n~, where n~ = 2, we have n ~ 3 . Thus

1 ~ n,~< 3,

(2)

0<~n4<~4.

(3)

It remains to examine systems of values ns, n~, n S which satisfy the inequalities (I)-

(3). System i. Let n~ = i. Then from (3) and (i), combined with n~ = 2, it follows that n s = 4; let x and y be vertices of degree 3, and x l, x 2, x~ and Y!, Y2, Y~ the vertices adjacent to x and y, respectively. Assume that x and y have a cor~non edge, (x, x 2) say, i.e.~ y = x 2 and x = Y2- Then, clearly x I = Yl and x 3 = Ys (Fig. 4). Since G also contains vertices other than x, xl, x2, x 3 and p(y) = 3, there exists a multiple edge (xl, x~), which means that p(x i) > 4 for i = 1 and i = 3. Let p(x I) = 5 and let z be the fifth vertex adjacent to x I. Since G is a triangulation, then z is also adjacent to x s. But G has no vertices of degree 2, and therefore z is adjacent to at least one other vertex, whence p(x 3) > 5~ i.e.~ only one vertex of degree ~ 5 may have common labeled edges with x and y. This means that, in addition to the five labeled edges incident on vertices of degree 3, there should be at least (2n 4 + 2n s - 2)/2 labeled edges, i . e . , m ' ~ 9 , a contradiction.

161

Fig. 4

Fig. 5

FiE. 6

Now assume that the vertices x and y do not have a common edge. situations are possible.

The following four

i. xi = Yi for i = i, 2, 3 (Fig. 5). Since the triangulation G should contain at least one other vertex in addition to x, x I, x 2, x 3, y, then x I say should be adjacent to one other vertex z, which is also adjacent to x 3. Clearly, there should exist a multiple edge (xl, x s) [since p(y) = 3], whence p (xi)>5, p ~ 8 ) ~ 5 and only for x 2 can we have p (x~)~5. This means that, in addition to the six labeled vertices incident on x and y, there should be at least (2n 4 + 2n s - 2)/2 labeled vertices, i . e . , m ' ~ 1 0 , a contradiction. 2. xl = Yl and x s = Ys (Fig. 6). If the vertices x I and x 3 are of degree~-~5, then p~)~6 and @ ~ ) ~ 6 . Indeed, since p ~,) = p(xs) = 5, the edge (x 2, Y2) exists. Since G is not (3; 3)-quasicolorable, we conclude that there exists at least one vertex z (in addition to x, y, x 2, Y2, xl = Yl, xs = Y3) which is adjacent to Y2, say. Since G is a triangulation, then z is also adjacent to x 2, and since p(x 3) = 5, there exists the multiple edge (x 2, Y2), i.e., p ~ , ) ~ 6 and p ~ , ) > 8 . This means that, in addition to the six labeled edges incident on the vertices of degree 3, there should be at least 2(n 4 + n s - 2)/2 labeled edges, i.e., m'>9, a contradiction. If three vertices of degree<~.5 coincide with the vertices Yl = xl, x2, Y2, xs = Ys, then clearly either p(xl) > 5 or p(x s) > 5. Hence it follows that in addition to the six labeled edges, there should be at least (2n~ + 2n s - 4)/2 labeled edges, i.e., m'>9, again a contradiction. 3. xa = Y3 (Fig. 7). Since 0(x 3) > 5, then at most four vertices of degree ~ 5 may coincide with xl, x2, Yx, and Y2. Hence m ' / > 6 + ( 2 n 4 + 2ns--4)/2 = 9, a contradiction. 4. xl ~ Yl for i = I, 2, 3. Vertices of degree_s.5 may coincide with the vertices xl, Yl, i = I, 2, 3, i . e . , m ' > 8 + (2n4 + 2n~--5)/2>8 , also a contradiction. These contradictions rule out System I. System 2. Let n~ = 2. Then the inequalities (3) and (i), combined with n 3 = 2, imply that a 5 > 2 . Assume that x and y are of degree 3, whereas xl, x2, x 3 and Yl, Y2, Ys are the vertices adjacent to x and y, respectively. Let x and y have a common labeled edge (Fig. 4). As for System I, we can show that only one vertex of degree 5 may coincide with x I or x 3. This means that m ' ~ 5 ~ - ( 3 a 4 , 1 +2a5--2)/2>8, i . e . , m ' ~ 9 , a contradiction. Now assume that x and y have no common edge.

The following four situations are possible.

i. xi = Yi for i = i, 2, 3 (Fig. 5). Since the triangulation G is not (3; 3)-quasicolorable, there exists at least one vertex z, other than y, x, x I = Yl, x2 = Y2~ x3 = Ys. This means that there should exist a multiple edge (xl, xs). These considerations imply that only x 2 may satisfy the inequality p (x2)~5. Thus, m ' / > 6 + ( 3 n 4 i ~ 2 n S - - 2 ) / 2 > 8 , a contradiction. 2. xl = Yl and x 3 = Ys (Fig. 6). If the vertices x I and x s are of degree ~ 5 , then the edge (x2, Y2) exists, and since G is not (3; 3)-quasicolorable, there exists at least one vertex z, other than x, y, x 2, Y2, xl = Yl, x3 = Ys- This means that p(x 2) > 4 and P(Y2) > 4, i.e., m ' ~ 8 ~ (3n4-]-~2ab~4)/2>8. if three vertices of degree ~.5 coincide with the vertices Yl = xl, x2, Y2, Ys = xs, then clearly either p(x I) > 5 or p(x 3) > 5, w h e n c e ~ ' ~ 6 - ~ (3a4--] ~- 2n5 ~ 4 ) ~ > 8, which is also a contradiction. 3. xs = Ys (Fig. 7). diction. 162

Since p(x s) > 5, then m ' > 6

+ (3al -| ~ 2 n b - - 4 ) / 2 > S J

a contra-

2

@

Fig. 7

Fig. 8

Fig. 9

4. Xl ~ Yl for i = i~ 2, 3. Since the vertices of degree-~<5 may coincide with x~ y, each of which is incident only on one labeled edge, then m'~6+(3n4--1+2ns--4)/2>8, a contradiction. These contradictions rule out System 2. System 3. Let n~ = 3. Then the inequalities (3) and (i), combined with ns = 2, give n5 ~0. Assume that the vertices x and y of degree 3 have a common edge, and xl, x2~ x 3 and Yl, Y2, Ys are adjacent to x and y, respectively. Let (x, x 2) be the common edge~ i.e,, y = x 2 and x = Y2 (Fig. 4). Since G is not (3; 3)-quasicoiorable, there should exist at least one vertex z other than x, x I = Yl, x2 = Y, x3 = Ys, and this means that there also exists a multiple edge (xl, x3). Hence clearly p(x l) > 4 and p(x 3) > 4, i.e.,

m'~>5+

3n4--I + 2

2n~

= 9,

a contradiction. Assume that the vertices x and y have no common edge.

Then four cases are possible.

I. xl = Yl for i = i, 2~ 3 (Fig. 5). Since the triangulation G is not (3~ 3)-quasicolorable, there should exist at least one vertex other than x, y, x I = Yl, i = It 2, 3, which means that there should exist a multiple edge (xl, x~), i.e., p(x l) > 4 and p(x~) > 4. Hence, m ' ~ 6 ~(3n4--I -~2n~--2)/2/>6-~ (3n~--3)/2 = 9 ~ a contradiction~ 2. xl = Y1 and x3 = Y3 (Fig. 6). Since p ~ 1 ) ~ 5 a n d at worst may coincide with x2, Y2, which means t h a t ~ ~ 6 3)/2 = 9, also a contradiction.

p @ 3 ) ~ 5 , the vertices of degree 4 ~- (3n~-- i -~ 2ns--~)/2 ~ 6-~ (3n4--

3. x~ = Y3 (Fig. 7). Since p(xs) > 4~ the vertex of degree 4 at worst may coincide with xl, x2~ Yl, and Y2~ each incident on one of the six labeled edges, which means that m' ~ 6 + ( 3 n 4 ~ 1 + 2n5 - 3)/2 ~ 6 + (3n4 - 4)/2 > 8 . 4.

xl r Yl for i = I, 2, 3.

As in 3 above, we can show that m' > 8, a contradiction~

The contradictions for all the three systems rule out Case 3. Case 4_i:n 3 = 3. Then the inequality (I) becomes 2n4-~-n~3. If no two vertices of degree 3 have a c o m m o n edge, the contradiction is obvious, since there are 9 labeled edges incident only on vertices of degree 3. Let the vertices x, y, z be of degree 3~ and let x and y have a common labeled edge. Assume that x is adjacent to xl, x2j x 3 and y to y~, y=, ys and that y = x=. As in System I of Case 2, we can show that either P(Xl) > 5 or 9(X~) > 5. At the same time, 2n~-~n~3, i.e.~ in addition to the three vertices of degree 3, there exist at least two vertices of degree ~ 5 , This means that, in addition to the eight labeled edges incident on vertices of degree 3, there should be at least one labeled edge, i.e~ m'~>9~ a contradiction. We have thus shown that for all possible values of n~, n~, ns satisfying the inequality (I), the number of labeled edges in the triangulation G is ~9, which contradicts the assump -, tion of the theorem. The contradiction proves Theorem I. Q.E.D. COROLLARY 1 (see [4

5]).

If G is a planar graph such that m ( G ) ~ 5 ,

then G6~Y~.

Note that the conditions used for our proof are unimprovable, which is clear from the exemple in Fig. 8. THEOREM 2. The planar h y p e ~ r a p h H = (X, E) is 3-colorable if ~ ( H ' ) ~ 2 and for any hypergraph edge e such that~ ~ X { ~ ' ) ~ , we have I ~ l ~ s ( H ) - - 5 . 163

As we have noted above, in order to prove this theorem it suffices to prove the following lemma. LEMMA.

Any planar graph G such that 8:(G~:~2 is (3; m(G E) - 5)-quasicolorable.

Proof. The proof is by induction on m(Gn~ For m(Gn)~-~8, the levm~a follows from Theorem i. Let the lemma be true for all m(G~) < t. We will prove it for m(G H) = t. Assume that the lemma is not true for m(G~) = t and G is the class of all planar graphs with minimum number of vertices and t labeled edges for which the lemma does not hold. Consider the graph G 6 G with minimum number of edges. Clearly, n2(G) = 0. As in Theorem I, we can show that all the edges incident on a vertex of degree 3 are labeled, i.e., n~(G) = 0. Consider a vertex Clearly, I ~ 4 . Without on x and all the faces that some faces r i and

x with at least one incident edge labeled. Let p(x) = s (Fig. 9). loss of generality, we may assume that two labeled edges are incident r1(x) , where i6[|,I--3], satisfy the condition IX(ri(x))l~t--5. Note rj may coincide. Consider the following two cases.

Case I. There are no multiple edges incident on x (Fig. 9). Remove the vertex x from G and add the edges(xs, xs), (X3,~)..... (xl-2,x~-0. The new graph G' contains t - 2 labeled edges, and therefore by the inductive hypothesis it is (3, t - 7)-quasicolorable. Having colored the graph G', restore G and color x in a color different from the colors of x I and xs It is easy to see that the result is a (3, t - 5)-quasicoloring for G. Case 2. There are multiple edges incident on x. Let x be incident on the edges (x, xl), ~, ~..,(x,x~) and let ~,Xl) , ~,xz) be labeled. Let r i be the face bordered by the edges (x, &+!), (x, Xi+=) i~ 6111,I-7 8]). If the vertices (x~§ &+2) are distinct for all the faces r i, then remove the vertex x from G and to each face r I add the edge Xl+l, X~+=. Note that some faces ri, rj with i # j may coincide. After this operation, each face F i is transformed into Fi such that IX(P~)l~t--& The resulting graph G' contains t - 2 labeled edges, and therefore, by the inductive hypothesis, it is (3; t - 7)-quasicolorable. Having colored G', restore G and color x in a color other than the colors of x I and xs leaving the colors of all the other vertices unchanged. It is easy to see that the result is a (3; t - 5)-quasicoloring for G, which contradicts the choice of G. Now assume that there is a face F i such that x~+l = x~+2. Let X~+l,y,,9~,;..,gm, x~+= = x~+1 be vertices other than x which lie on the border of the face r i, and all Yl are pairwise distinct. Remove the vertex x from G and add the edges (xi+1,~+@ to each face rj for which ~§ to each fact of type r i add the edge ~t+*,Y~ Since the resulting graph G' contains t - 2 labeled edges, it is (3; t - Z)-quasicolorable. Having colored G', we may obtain a (3; t - 5)-quasicoloring for G. The contradiction proves Lemma i. COROLLARY 2.

If G is a planar graph such that s(~.~<2and m(O)<~.k + 5, then,

G6Wk.

In conclusion, we would like to pose another related problem. Problem.

If G is a planar 3-colorable graph such that m(G)~.~k + 5, then G6W~. LITERATURE CITED

I.

2. .

4. .

164

C. Berge, Graphes et hypergraphes, Dunod, Paris (1970). M. Garey and D. Johnson, Computers and Intractability[Russian translation], Mir, Moscow (1982). F. Harary, Graph Theory, Addison-Wesley, New York (1969). M. I. Burshtein, "On the chromatic number of planar hypergraphs," Soobshch. Akad. Nauk SSR, 84, No. i, 45-48 (1976). P. Hits, "On 3-chromatic planar hypergraphs," Math. Slovaka, 31, No. i, 79-82 (1981).