On a Conjecture by Plummer and Toft Mirko Horňák and Stanislav Jendrol’ DEPARTMENT OF GEOMETRY AND ALGEBRA P. J. ŠAFÁRIK UNIVERSITY JESENNÁ 5, 041 54 KOŠICE, SLOVAKIA E-mail: hornak@turing.upjs.sk, jendrol@kosice.upjs.sk Received August 27, 1996; accepted August 29, 1998 Abstract: The cyclic chromatic number χc (G) of a 2-connected plane graph G is the minimum number of colors in an assigment of colors to the vertices of G such that, for every face-bounding cycle f of G, the vertices of f have different colors. Plummer and Toft proved that, for a 3-connected plane graph G, under the assumption ∆∗ (G) ≥ 42, where ∆∗ (G) is the size of a largest face of G, it holds that χc (G) ≤ ∆∗ (G)+4. They conjectured that, if G is a 3-connected plane graph, then χc (G) ≤ ∆∗ (G) + 2. In the article the conjecture is proved for ∆∗ (G) ≥ 24. c 1999 John Wiley & Sons, Inc. J Graph Theory 30: 177–189, 1999 Keywords: plane graph, cyclic coloring, cyclic chromatic number 1. INTRODUCTION In this article we consider 2-connected plane graphs without loops and multiple edges. Let G be such a graph and let x be a vertex or a face of G. The degree of x, in symbol deg(x), is the number of edges incident with x. By ∆∗ (G) we denote the maximum face degree of G. A cyclic coloring of a plane graph G is such a coloring of the vertices of G that, if two vertices are incident with a common face, they receive different colors. Let a k -coloring of a graph G be a coloring of G using k colors. The cyclic chromatic number (introduced by Ore and Plummer [15]) of a graph G, denoted χc (G), is the minimum k such that G has a cyclic k -coloring. Obviously, ∆∗ (G) ≤ χc (G). For Correspondence to: S. Jendrol’ Contract grant sponsor: Slovak VEGA Contract grant number: 1/4377/97 c 1999 John Wiley & Sons, Inc. CCC 0364-9024/99/030177-13 178 JOURNAL OF GRAPH THEORY the graph P of a 3-sided prism it holds χc (P ) = 6 = ∆∗ (P ) + 2. In a recent book Jensen and Toft [14] have posed the following two questions (see Problem 2.5): (1) Is χc (G) ≤ 32 ∆∗ (G)? (2) If G is 3-connected, is χc (G) ≤ ∆∗ (G) + 2? Question 1 is still open. For a recent progress in solving it, consult the article Borodin et al. [6], where it is proved that χc (G) ≤ 95 ∆∗ (G). The present article is devoted to Question 2. Plummer and Toft [16] proved that χc (G) ≤ ∆∗ (G) + 9 in general and, among other similar results, χc (G) ≤ ∆∗ (G)+4 if ∆∗ (G) ≥ 42. In the same article (see also [14]) they have conjectured (PTC) that χc (G) ≤ ∆∗ (G)+2. The validity of PTC for G with ∆∗ (G) = 3 follows from the Five Color Theorem by Heawood [11]; moreover, the Four Color Theorem by Appel and Haken [2] yields a stronger statement, namely χc (G) ≤ ∆∗ (G)+1 = 4. For ∆∗ (G) = 4, PTC has been proved by Borodin [4]. For ∆∗ (G) ≥ 24 it is known that χc (G) ≤ ∆∗ (G) + 3—the result has been obtained independently by Borodin [5] and Horňák and Jendrol’ [12]. Recently, rapid progress in the area can be seen: Borodin and Woodall [7] proved PTC for ∆∗ (G) ≥ 61. Further, they proved that χc (G) ≤ ∆∗ (G) + 1 if ∆∗ (G) ≥ 122; Enomoto et al. [9] improved this to ∆∗ (G) ≥ 60. Graphs of pyramids (i.e., plane embeddings of wheels) show that the upper bound ∆∗ (G) + 1 is best possible. We found a Lebesgue type result, which enabled us to show in [13] that PTC is true provided that ∆∗ (G) ≥ 40. Borodin and Woodall [8] proved that χc (G) ≤ ∆∗ (G) + 3 if ∆∗ (G) ≥ 21. The aim of this article is to make a further step in tackling PTC—to prove the following. Theorem. For any 3-connected plane graph G, χc (G) ≤ max{∆∗ (G) + 2, 26}. PTC is open for graphs G with 5 ≤ ∆∗ (G) ≤ 23. The best known estimates for χc (G) in these cases are: ∆ ∗ (G ) 5 6 7 8 9 10 11 12 13, 14, 15, 16 17, 18 19, 20 21, 22, 23 χc (G) 8 10 12 13 15 17 19 20 21 ∆∗ (G) + 5 ∆∗ (G) + 4 ∆∗ (G) + 3 Reference Borodin et al.[6] Borodin [3] Horňák and Jendrol’ [12] [12], Borodin [5] Borodin and Woodall [8] ON A CONJECTURE BY PLUMMER AND TOFT 179 2. PRELIMINARIES Let G be a 3-connected graph with at least five vertices and let xy be an edge of G. By G(x → y) we denote the graph formed by adding to G − x all the edges yz such that the vertex z = / y is adjacent (in G) to x, but not to y . Evidently, the graphs G(x → y) and G(y → x) are isomorphic, and the edge xy is said to be contractible, if the graph G(x → y) is 3-connected. By G\xy we denote the graph formed from G − xy by smoothing all (possibly arisen) 2-vertices. If G is a plane graph, then both G(x → y) and G\xy are also plane graphs, and ∆∗ (G(x → y)) ≤ ∆∗ (G). Two vertices x, y of G are defined to be cyclically adjacent if they are incident with a common face of G. Let the cyclic degree of a vertex x, in symbol cd(x), be the number of vertices that are cyclically adjacent to x. The cyclic neighborhood of a vertex x is the set of all vertices that are cyclically adjacent to x. If a vertex or a face of G is of degree n, it is said to be an n-vertex or an n-face, respectively. Let x be an n-vertex incident with faces f1 , . . . , fn in a natural order (when rotating around x) and let deg(fi ) = di , i = 1, . . . , n; we will refer to xPas to a (d1 , . . . , dn )-vertex. For the cyclic degree of x we clearly have cd(x) = ni=1 (di − 2). For integers p, q , we denote by [p, q] the interval of all integers between p and q (inclusively). Proposition 1. Any partial cyclic k -coloring of a graph G in which the set of uncolored vertices consists only of either (i) a vertex x with cd(x) ≤ k − 1 or (ii) cyclically adjacent vertices x, y with cd(x) ≤ k − 1 and cd(y) ≤ k may be extended to a cyclic k -coloring of G. Proof. The cyclic neighborhood of x has cardinality cd(x); this provides an extension in the case (i). In the case (ii), we color first y and then x. We need a result of Halin [10]. Lemma 1. Let G be a 3-connected graph with at least five vertices. Then any 3-vertex of G is incident with a contractible edge. From a result of Ando et al. [1], Lemma 2 follows. Lemma 2. Let G be a 3-connected graph with at least five vertices. If a vertex x of G with deg(x) ≥ 4 is incident with no contractible edge, then it is adjacent to three 3-vertices. First we will show that a counterexample to our theorem, which is minimal with respect to the number of edges, cannot contain certain configurations. Some of them are in Figs. 1(a)–(f) and 2(a), where encircled numbers are degrees of corresponding vertices and 4+ means that a corresponding vertex is of degree ≥ 4. (An empty circle corresponds to a vertex of an arbitrary degree.) 180 JOURNAL OF GRAPH THEORY FIGURE 1. Lemma 3. Let G be a 3-connected plane graph with a smallest number of edges such that χc (G) > max{∆∗(G) + 2, 26}. Then G contains none of the following configurations: 1. a configuration from Figs. 1(a)–(f), where, in Fig. 1(e), deg(f1 ) ≤ ∆∗ (G) − 1, and, in Fig. 1(f), deg(f1 ) + deg(f2 ) ≤ 2∆∗ (G) − 1; 2. a configuration from Fig. 2(a), where cd(x) ≤ ∆∗ (G) + 1 and deg(fi ) ≥ 5, i = 1, 3; 3. a k -vertex x, k ≥ 4, with cd(x) ≤ ∆∗ (G) + 1, which is either ON A CONJECTURE BY PLUMMER AND TOFT 181 FIGURE 2. (i) incident with a contractible edge xy or (ii) adjacent to a 3-vertex y with cd(y) ≤ ∆∗ (G) + 2; 4. a 3-vertex x with cd(x) ≤ ∆∗ (G) + 1. Proof. (For simplicity we will write ∆∗ instead of ∆∗ (G).) Suppose that G possesses some of the configurations above. By modifying G, we will define a 3-connected plane graph G0 with |E(G0 )| < |E(G)| and ∆∗ (G0 ) ≤ ∆∗ . Then χc (G0 ) ≤ m0 := max{∆∗ (G0 ) + 2, 26} ≤ m := max{∆∗ + 2, 26} and there exists a cyclic m0 -coloring ϕ of G0 . This coloring will serve as a basis for finding a cyclic m-coloring ψ of G, which is in contradiction with χc (G) > m. All values of ψ not defined explicitly are ‘‘inherited’’ from ϕ, i.e., ψ(v) := ϕ(v) for (some) vertices v ∈ V (G) ∩ V (G0 ). 1. If G has a configuration of Fig. 1 we define G0 := G\x1 x2 for figures (a)– (e), and G0 := G(x1 → x0 ) for figure (f), where the face f1 (incident with the contracted edge x0 x1 ) has been chosen in such a way that deg(f1 ) ≤ ∆∗ − 1. Let C(fk ) be the set of colors used in the coloring ϕ for the vertices of the face fk . (a)–(b): If ϕ(y) ∈ C(fk ) for some k ∈ {1, 2}, then we can extend ϕ to ψ by coloring first x3−k and next xk , because in such a case at most ∆∗ +1 colors are used in the cyclic neighborhood of each of x1 , x2 at the time when it is colored. (Note that ϕ(y) is used twice in the cyclic neighborhood of xk because of 3-connectedness / C(f1 ) ∪ C(f2 ), we may recolor z of G.) On the other hand, provided that ϕ(y) ∈ with ϕ(y) to create the situation above. (c): If ϕ(z1 ) ∈ / C(f2 ), putting ψ(x2 ) := ϕ(z1 ), we have at least one color for x1 . If ϕ(z1 ) ∈ C(f2 ), we remove the color from y2 , define ψ(x2 ) := ϕ(y2 ), and / f2 , since G is 3-connected.) then color first x1 and next y2 . (We have f1 = (d): Since ϕ(w1 ) = / ϕ(w2 ), we may assume that ϕ(w1 ) = / ϕ(z). Also, we may assume that ϕ(w1 ) ∈ C(f2 ), because otherwise we may recolor y2 with ϕ(w1 ). Now, color x1 , then color x2 . (e): Take simply ψ := ϕ. (f): We have deg(f1 ) ≤ ∆∗ − 1. Thus, if {ϕ(y1 ), ϕ(y2 )} ∩ C(f1 ) = / ∅, at / C(f1 ) ∪ C(f2 ) for least one color is available for the vertex x1 . If ϕ(yk ) ∈ some k ∈ {1, 2}, we may recolor the vertex z with ϕ(yk ) to obtain the preceding 182 JOURNAL OF GRAPH THEORY situation. Finally, if {ϕ(y1 ), ϕ(y2 )} ∩ C(f1 ) = ∅ and {ϕ(y1 ), ϕ(y2 )} ⊆ C(f2 ), we may remove the color from x2 and then color first x1 and next x2 . 2. In this case, we form G0 by replacing the configuration from Fig. 2(a) by that from Fig. 2(b), where the edge e = y1 y2 is added if and only if deg(f2 ) ≥ 4, and make use of Proposition 1.(i). 3.(i) After setting G0 := G(y → x) we employ Proposition 1.(i). 3.(ii) By Lemma 1, the vertex y is incident with a contractible edge yz . By 3.(i), we may assume that z = / x. We define G0 := G(y → z), remove the color from the vertex x, and use Proposition 1.(ii). 4. Lemma 1 yields a contractible edge xy—this allows us to use Proposition 1.(i). 3. PROOF OF THEOREM The proof is by induction on the number of edges of G. Evidently, there is nothing to prove if |E(G)| ≤ 40, because in such a case |V (G)| ≤ 26—the assumption |V (G)| ≥ 27 would yield |E(G)| ≥ d 3·27 2 e = 41. Suppose that our Theorem is not true and G = (V, E, F ) is a counterexample to it with a minimum number of edges. With respect to the results mentioned in the introduction, we know that then ∆∗ = ∆∗ (G) ≥ 24. Euler’s formula for G may be rewritten as X 2(3 − deg(v)) + v∈V −12 = X (6 − deg(f )) = 12, f ∈F X (2 deg(v) − 6) + v∈V = X v∈V = X X X deg(f ) − 6 f ∈F v∈f (2 deg(v) − 6) + X X deg(f ) − 6 v∈V f 3v 2 deg(v) − 6 + v∈V deg(f ) deg(f ) X deg(f ) − 6 f 3v deg(f ) . Thus, if we define the charge of a vertex v ∈ V by c(v) := 2 deg(v) − 6 + X deg(f ) − 6 f 3v deg(f ) , then the sum of all the charges of vertices in G is negative; in this way we obtain a charge mapping c ∈ QV . We will create a new charge mapping c0 ∈ QV as a redistribution of c, i.e., X v∈V c0 (v) = X v∈V c(v) = −12. ON A CONJECTURE BY PLUMMER AND TOFT 183 This new charge mapping leads to a contradiction, since it is possible to find a decomposition D of V such that X c0 (v) ≥ 0 for any D ∈ D. (∗) v∈D We will denote by D(v) the set of D containing v ∈ V . In fact, nontrivial (containing more than one element) sets in D consist of 3-vertices only. To obtain the new charge mapping c0 , the charges of c are redistributed by the following two Rules, where, in Rule 1, V (f ) is the set of vertices incident with a face f and V3 (f ) := {v ∈ V (f ) : deg(v) = 3}: / ∅ = / V (f ) − V3 (f ). Then any Rule 1. Let f be a 3-face such that V3 (f ) = vertex y ∈ V (f ) − V3 (f ) sends to any vertex z ∈ V3 (f ) the amount t(y, z) = −c(z)/|V (f ) − V3 (f )|. Rule 2. If z is a (4, 4, ∆∗ )-vertex, any of its neighbors y of degree ≥ 4 sends to z the amount t(y, z) = −c(z) = ∆6∗ . Observe that the notation t(y, z) used in Rules is correct—if vertices y, z are adjacent and deg(y) ≥ 4, deg(z) = 3, then y can send an amount to z by at most one of Rules 1, 2, and, from Lemma 3.4, there is at most one 3-face incident with yz for which Rule 1 can be applied. If v ∈ V is a (d1 , . . . , dn )-vertex adjacent to vertices v1 , . . . , vn in such a way that the edge vvi is incident with faces of degrees di and di+1 (indices are taken modulo n), then c(v) = 2n−6+ n X di − 6 i=1 di = n X i=1 6 6 3− − di n = n X i=1 3 3 6 3− − − . di di+1 n Setting γ(d1 , . . . , dn ) := 2n − 6 + n X di − 6 i=1 σ(k, l, m) := 3 − di , 3 3 6 − − k l m p(v, vi ) := σ(di , di+1 , n) yields c(v) = γ(d1 , . . . , dn ) = n X i=1 σ(di , di+1 , n) = n X p(v, vi ). i=1 Thus, the charge of the vertex v may be counted in a natural way as the sum −→ of partial charges p(v, vi ) corresponding to the oriented edges vvi leaving v, i = −→ 1, . . . , n. If we define the new partial charge of vvi P by p0 (v, vi ) := p(v, vi ) − t(v, vi ), then the new charge of the vertex v is c0 (v) = ni=1 p0 (v, vi ). 184 JOURNAL OF GRAPH THEORY In our analysis, two properties of the function γ(d1 , . . . , dn ) are needed. Clearly, γ(d1 , . . . , dn ) = γ(dπ(1) , . . . , dπ(n) ) for any permutation π of [1, n]. The next Lemma provides a lower bound for the charge of a vertex v incident with faces of degrees d1 , . . . , dq , d0q+1 , . . . , d0n , where d0i ≥ di and d0n ≥ di for P P i ∈ [q + 1, n − 1] and the weight of v, qi=1 di + ni=q+1 d0i , is at least w. q and for positive integers n, d1 , . . . , dn−1 , Lemma 4. For a nonnegative integer Pn−1 w with n ≥ q + 2 and w ≥ d i=1 i + max{di : i ∈ [q + 1, n − 1]} let Sq (d1 , . . . , dn−1 ; w) denote the set of all integer sequences (d1 , . . . , dq , d0q+1 , . . . , P d0 ) in which d0i ≥ di and d0n ≥ di for all i ∈ [q + 1, n − 1] and qi=1 di + Pnn 0 0 0 i=q+1 di ≥ w. Then the minimum of γ(d1 , . . . , dq , dq+1 , . . . , dn ) over Sq (d1 , . . . , Pn−1 dn−1 ; w) is equal to γ(d1 , . . . , dn−1 , w − i=1 di ). P Proof. We have γ(d1 , . . . , dq , d0q+1 , . . . , d0n ) = 3n − 6 − 6 qi=1 d1i P − 6 ni=q+1 d10 . Let us decrease d0i to di while increasing d0n by d0i − di for any i i ∈ [q + 1, n − 1] with d0i > di . Since for positive integers a1 , a2 , a3 , a4 with a1 + a2 = a3 + a4 and a1 < min{a3 , a4 } it holds −( a11 + a12 ) < −( a13 + Pn−1 00 00 1 0 0 i=q+1 (di − di ) we obtain γ(d1 , . . . , dn−1 , dn ) ≤ a4 ), putting dn := dn + γ(d1 , . . . , dq , d0q+1 , . . . , d0n ). Here the inequality turns into equality if and only 00 all i ∈ [q + 1, n − 1], or, equivalently, dn = d0n . In such a case, if d0i = di for P n−1 d0n ≥ w − i=1 di ≥ max{di : i ∈ [q + 1, n − 1]} ≥ 1 and, as the sequence 1 ∞ {− m }m=1 is increasing, the proof follows. It is easy to find an upper bound for the amount t(y, z) sent from y to z . Namely, if y sends something to z by Rule 1, then z is a (3, k, l)-vertex. By Lemma 3.4, cd(z) = k + l − 3 ≥ ∆∗ + 2, so that min{k, l} ≥ 5. Hence, from Lemma 4 with q = 1, d1 = 3, d2 = 5, and w = ∆∗ +8, we obtain γ(3, k, l) ≥ γ(3, 5, ∆∗ ) = − 15 − 6 1 6 9 9 ∆∗ ≥ − 5 − 24 = − 20 . Thus, we have either t(y, z) = −c(z) = −γ(3, k, l) ≤ 20 9 or t(y, z) = − 12 c(z) ≤ 40 . If y makes a transfer to z with respect to Rule 2, then 6 1 t(y, z) = ∆∗ ≤ 4 . Now we are going to define the sets D(v), v ∈ V , in such a way that (*) is fulfilled. Suppose that v is a (d1 , . . . , dn )-vertex adjacent to vertices v1 , . . . , vn and that, for any i ∈ [1, n], the edge vvi is incident with di -face fi and di+1 -face fi+1 . (1). If n = 3, then, without loss of generality, d1 ≤ d2 ≤ d3 . (We may choose as f1 any face incident with v and we may choose also one of two possible orientations to rotate around v .) (11). If d1 = 3, then, by Lemma 3.4, cd(v) = d2 + d3 − 3 ≥ ∆∗ + 2, hence d2 ≥ 5. (111). If max{deg(v1 ), deg(v3 )} ≥ 4, then, because of Rule 1, c0 (v) = 0 and we may set D(v) := {v}. ON A CONJECTURE BY PLUMMER AND TOFT 185 (112). Now suppose that deg(v1 ) = deg(v3 ) = 3; then c0 (v) = c(v) and c0 (vi ) = c(vi ), i = 1, 3. If d01 is the degree of the face adjacent to f1 along the edge v1 v3 , then, by Lemma 3.1. (a), min{d01 , d2 , d3 } ≥ 6. We are going to show that c0 (v) + c0 (v1 ) + c0 (v3 ) ≥ 0, which will allow us to define D(v) := {v, v1 , v3 }. (1121). The assumption d2 = 6 forces (see Lemma 3.1. (f)) the vertex v3 to be ∗ = a (3, ∆∗ , ∆∗ )-vertex. In such a case c0 (v) + c0 (v1 ) + c0 (v3 ) = −3 + 4 · ∆∆−6 ∗ 24 1 − ∆∗ ≥ 0. (1122). d2 ≥ 7. (11221). If d01 = 6, then, by Lemma 3.1.(f), d2 = d3 = ∆∗ and c0 (v) + c0 (v1 ) + 24 c0 (v3 ) = 1 − ∆ ∗ ≥ 0. (11222). For d01 ≥ 7, we have d := min{d01 , d2 } ≥ 7. (112221). If d ∈ [7, 11], the remaining (besides d) terms of the triple (d01 , d2 , d3 ) are at least ∆∗ + 5 − d (by Lemma 3.4), so that c0 (v) + c0 (v1 ) + c0 (v3 ) = 3 − 12 24 ∗ − d122 − d123 ≥ 3 − 12 d − ∆∗ +5−d . Using ∆ ≥ 24, it is easy to see that the last d0 1 expression is lower bounded by 3 − 12 7 − 24 ∆∗ −2 ≥ 9 7 − 24 22 > 0. (112222). d ∈ [12, ∆∗ ] implies c0 (v) + c0 (v1 ) + c0 (v3 ) ≥ 3 − 36 d ≥ 0. (12). d1 = 4. (121). If d2 = 4, then, by Lemma 3.4, d3 = ∆∗ . Let m be the number of neighbors of v of degree ≥ 4. (1211). If m = 0, then c0 (v) = c(v) = − ∆6∗ . Again by Lemma 3.4, v1 is a 0 v (4, 4, ∆∗ )-vertex and fi = vv1 v4−i 4−i , i = 1, 2. 0 ) = 3, then, by Lemmas 3.1. (c) and (12111). If there is i ∈ {1, 2} with deg(v4−i 0 v 3.1. (d), the face adjacent to fi along the edge v4−i 4−i is of degree k ≥ 6 and 3 6 0 0 0 0 c (v4−i ) = c(v4−i ) = c (v4−i ) = c(v4−i ) = 2 − k − ∆6∗ . Since c0 (v1 ) ≥ c(v1 ) = P − ∆6∗ , the estimate x∈V (fi ) c0 (x) ≥ 2 · (− ∆6∗ ) + 2 · ( 32 − k6 − ∆6∗ ) ≥ 3 − 12 6 − 24 24 = 0 enables us to set D(v) := V (fi ). (12112). If min{deg(v20 ), deg(v30 )} ≥ 4, then, by Rule 2, c0 (v1 ) = c(v1 ) − 2c(v1 ) = ∆6∗ and, with respect to c0 (v) + c0 (v1 ) = 0, we define D(v) := {v, v1 }. Note that Lemma 3.1. (c) guarantees that for any two (4, 4, ∆∗ )-vertices u1 , u2 with no neighbor of degree ≥ 4 we have either D(u1 ) = D(u2 ) or D(u1 ) ∩ D(u2 ) = ∅. (1212). If m ≥ 1, we may suppose that D(u) is already determined for all (4, 4, ∆∗ )-vertices u having no neighbor of degree ≥ 4. If v is in no such D(u), we may put D(v) := {v}, because of c0 (v) = c(v) − mc(v) = 6(m−1) ≥ 0. ∆∗ (122). For d2 ≥ 5, we assume that D(u) is already defined for all (4, 4, ∆∗ )vertices. If v does not belong to any such D(u), we set D(v) := {v}—we have, by Lemma 3.4, d2 + d3 ≥ ∆∗ + 4 and, by Lemma 4, c0 (v) = c(v) ≥ γ(4, 5, 3 3 6 ∆∗ − 1) = 10 − ∆∗6−1 ≥ 10 − 23 > 0. 186 JOURNAL OF GRAPH THEORY (13). For d1 ≥ 5, analogously as above, c0 (v) = c(v) ≥ γ(5, 5, ∆∗ − 2) ≥ 3 6 5 − 22 > 0 and D(v) := {v}. (2). For n ≥ 4, showing that c0 (v) ≥ 0 will allow us to set D(v) := {v}. (21). n = 4. (211). cd(v) ≤ ∆∗ + 1: By Lemma 3.3.(i) there is no contractible edge incident with v , hence, by Lemma 2, v is adjacent to at least three 3-vertices. By Lemmas 3.1. (e) and 3.4, there is no i ∈ [1, 4] such that di = di+1 = 3. Because cd(v) ≤ ∆∗ +1, 3.2, and 3.4, no face incident with v is of degree ∆∗ Now, by Lemmas 3.1. (e), P all faces incident with v are of degree ≥ 4; then c(v) = 6 − 6 4i=1 d1i ≥ 6 − P 6 4i=1 14 = 0. On the other hand, by Lemma 3.3.(ii), t(v, vi ) = 0, i = 1, 2, 3, 4, and c0 (v) = c(v) ≥ 0. (212). If cd(v) ≥ ∆∗ + 2, then m := |{i ∈ [1, 4] : deg(fi ) = 3}| ≤ 2. (2121). m = 2. (21211). Suppose that v is incident with two adjacent 3-faces, say, f2 and f3 . Then, by Lemmas 3.1. (e) and 3.4, deg(vi ) ≥ 4, i = 1, 2, 3. From Lemma 4 we know that c(v) ≥ γ(3, 3, 4, ∆∗ ) = 12 − ∆6∗ ≥ 14 and, as t(v, vi ) = 0, i = 1, 2, 3, and t(v, v4 ) ≤ 14 (v can send something to v4 only by Rule 2), c0 (v) ≥ 0. (21212). Now let v be incident with two nonadjacent 3-faces, say, f2 and f4 . We v ) + p0 (v, v4 ) ≥ 0 will show that p0 (v, v1 ) + p0 (v, v2 ) ≥ 0; the inequality p0 (v, P2 3 can be proved similarly. We have p(v, v1 ) + p(v, v2 ) = i=1 σ(di , di+1 , 4) = 1 − d31 − d33 , which is, because of d1 + d3 ≥ ∆∗ + 4, lower bounded by 1 − 34 − 3 1 ∆∗ ≥ 8 . Thus, it is sufficient to analyze the case t(v, v1 ) + t(v, v2 ) > 0, for which min{deg(v1 ), deg(v2 )} = 3. (212121). If exactly one of v1 , v2 is of degree 3, say, deg(v1 ) = 3 < deg(v2 ), then, by Lemmas 3.1. (e) and 3.4, d1 ≥ 5 and d3 = ∆∗ ; in this case t(v, v1 ) = 9 − 12 c(v1 ) ≤ 40 , t(v, v2 ) = 0, and p0 (v, v1 ) + p0 (v, v2 ) = 1 − d31 − ∆3∗ + 12 c(v1 ) ≥ 3 9 1 − 40 = 20 . 1 − 35 − 24 (212122). Now let deg(v1 ) = deg(v2 ) = 3. Let d02 be the degree of the face adjacent to f1 along the edge v1 v2 . Then, by Lemma 3.4, d1 + d02 ≥ ∆∗ + 5. We may assume that d1 ≤ d3 . Since t(v, v1 ) + t(v, v2 ) = −c(v1 ) − c(v2 ) = −2 + d61 + d120 + d63 ≤ −2 + d121 + d120 , we may suppose that min{d1 , d02 } ≤ 11. We 2 2 have to estimate p0 (v, v1 ) + p0 (v, v2 ) = 3 − 9 d1 − 12 d02 − 9 d3 . (2121221). If d1 ≤ 11, then, with respect to min{d02 , d3 } ≥ ∆∗ + 4 − d1 , p0 (v , 21 21 v1 ) + p0 (v , v2 ) ≥ 3 − d91 − ∆∗ +4−d ≥ 3 − d91 − 28−d ≥ 3 − 95 − 21 23 > 0. 1 1 (2121222). If d02 ≤ 11, then d3 ≥ d1 ≥ ∆∗ +5−d02 . Since d02 ≥ 6 by Lemma 3.1. 18 12 18 12 18 (b), p0 (v, v1 )+p0 (v, v2 ) ≥ 3− d120 − ∆∗ +5−d 0 ≥ 3− d0 − 29−d0 ≥ 3− 6 − 23 > 0. 2 2 2 2 ON A CONJECTURE BY PLUMMER AND TOFT 187 (2122). m = 1: Without loss of generality, assume that d2 = 3. Set r := |{i ∈ {1, 2} : deg(vi ) = 3}|. (21221). If r = 0, then t(v, vi ) = 0, i = 1, 2, and t(v, vi ) ≤ 14 , i = 3, 4 (here only Rule 2 can be applied). From Lemma 4, it follows c(v) ≥ γ(3, 4, 4, ∆∗ − 1) = 17 1 0 1 − ∆∗6−1 ≥ 17 23 , so that c (v) ≥ 23 − 2 · 4 > 0. (21222). For r = 1, we may assume that deg(v1 ) = 3. Then t(v, P v2 ) = 0 and, by Lemma 3.4, d1 ≥ 5. With respect to d4 ≥ 4 then t(v , v4 ) = 0 and 4i=1 t(v, vi ) ≤ 9 1 19 ∗ 40 + 4 = 40 . On the other hand, by Lemma 4, c(v) ≥ γ(3, 4, 5, ∆ − 2) = 13 6 13 6 19 10 − ∆∗ −2 ≥ 10 − 22 > 40 . (21223). If r = 2, then, by Lemma 3.4, d1 , d3 ≥ 5. As in (21212), we have p0 (v, v1 ) + p0 (v, v2 ) ≥ 0. Thus, it will be sufficient to prove that p0 (v, v3 ) + p0 (v, v4 ) ≥ 0. It holds p(v, v3 ) + p(v, v4 ) = 3 − d31 − d33 − d64 ≥ 3 − 2 · 35 − 64 = P4 3 1 3 i=3 t(v, vi ) ≤ 4 < 10 . However, the mentioned 10 , hence, we are done if sum can be greater than 14 only if d1 = d3 = ∆∗ and d4 = 4; in such a case p0 (v, v3 ) + p0 (v, v4 ) = 3 − 2 · ∆3∗ − 64 − 2 · ∆6∗ > 0. (2123). If m = 0, then, by Lemma 4, c(v) ≥ γ(4, 4, 4, ∆∗ − 2) = 32 − ∆∗6−2 ≥ 1 and c0 (v) ≥ 27 22 − 4 · 4 > 0. 27 22 (22). n = 5. (221). For cd(v) ≤ ∆∗ + 1, we know from Lemma 3.3.(i) that there is no contractible edge incident with v , hence, by Lemma 2, at least three from among neighbors of v are of degree 3. Therefore, by Lemmas 3.1. (e) and 3.4, there is no i ∈ [1, 5] with di = di+1 = 3. We are going to show that p0 (v, vi ) > 0 for any i ∈ [1, 5]. If deg(vi ) ≥ 4, then p0 (v, vi ) = p(v, vi ) ≥ 3 − 33 − 34 − 65 > 0. For deg(vi ) = 3 and min{di , di+1 } ≥ 4, we have p0 (v, vi ) ≥ (3 − 2 · 34 − 65 ) − 14 > 0. Finally, suppose that deg(vi ) = 3 and, without loss of generality, di = 3. By Lemma 3.3.(ii), cd(vi ) ≥ ∆∗ + 3. Therefore, if fi shares the edge vi−1 vi with a d0i -face, then d0i + di+1 ≥ ∆∗ + 6 and p0 (v, vi ) = σ(3, di+1 , 5) + γ(3, d0i , di+1 ) = 9 1 1 3 9 1 1 3 3 6 0 5 − 6( d0 + di+1 ) − di+1 ≥ 5 − 6( 6 + ∆∗ ) − 6 ≥ 10 − 24 > 0. Thus, c (v) is a i sum of positive summands. (222). cd(v) ≥ ∆∗ + 2. (2221). Suppose first there is a 3-face incident with v , say, f2 . Without loss of generality, assume that it is incident with the maximum number, say q , of 3-vertices, from among all 3-faces incident with v . (22211). If q = 2, then, by Lemma 3.4, min{d1 , d3 } ≥ 5, and, by Lemma 4, 6 23 23 9 0 c(v) ≥ γ(3, 3, 5, 5, ∆∗ − 4) = 13 5 − ∆∗ −4 ≥ 10 , so that c (v) ≥ 10 − 5 · 20 > 0. (22212). For q = 1 assume, without loss of generality, that deg(v1 ) ≥ 4. Then, by Lemmas 3.1. (e) and 3.4, d1 = ∆∗ and d3 ≥ 5. Also, we have t(v, v1 ) = 0 and 9 t(v, v2 ) ≤ 40 . 188 JOURNAL OF GRAPH THEORY (222121). For d4 = d5 = 3, we obtain deg(v4 ) ≥ 4 and t(v, v4 ) = 0, so that 9 9 6 c0 (v) ≥ (3 − ∆6∗ − d63 ) − ( 40 + 2 · 20 ) ≥ 3 − 24 − 65 − 98 > 0. (222122). If max{d4 , d5 } ≥ 4, then c0 (v) ≥ (7 − ∆6∗ − 6 7 − 24 − 65 − 63 − 64 − 63 40 > 0. P5 9 9 6 i=3 di ) − ( 40 + 3 · 20 ) ≥ (22213). If q = 0, then t(v, vi ) = 0, i = 1, 2. (222131). If v is incident with at most three 3-faces, then, by Lemma 4, c(v) ≥ γ(3, 3, 3, 4, ∆∗ − 1) = 32 − ∆∗6−1 ≥ 57 46 and, since v can send out something only 57 1 0 by Rule 2, c (v) ≥ 46 − 3 · 4 > 0. (222132). If v is incident with four 3-faces, then c0 (v) = c(v) = γ(3, 3, 3, 3, ∆∗ ) = 1 − ∆6∗ ≥ 34 . (2222). If min{d1 , . . . , d5 } ≥ 4, then p(v, vi ) = 3 1 and p0 (v, vi ) ≥ 10 − 14 = 20 so that c0 (v) ≥ 14 . 9 5 − 3 di − 3 di+1 ≥ 9 5 −2· 3 4 = 3 10 (23). n = 6. (231). Suppose first cd(v) ≤ ∆∗ + 1. If deg(vi ) ≥ 4, then p0 (v, vi ) = p(v, vi ) ≥ 3 − 2 · 33 − 66 = 0. For deg(vi ) = 3, we may proceed as in (221) to see that p0 (v, vi ) > 0. We conclude that c0 (v) is a sum of nonnegative summands. (232). If cd(v) ≥ ∆∗ + 2, Lemma 4 yields c(v) ≥ γ(3, 3, 3, 5, 5, ∆∗ − 5) = 18 6 312 312 9 0 5 − ∆∗ −5 ≥ 95 and c (v) ≥ 95 − 6 · 20 > 0. 3 3 (24). The assumption n ≥ 7 leads to p(v, vi ) ≥ 15 7 − di − di+1 > 0 for all i ∈ [1, n]. If t(v, vi ) > 0 and min{di , di+1 } = 3, then max{di , di+1 } ≥ 5 (Lemma 19 9 0 3.4) and p(v, vi ) = σ(di , di+1 , n) ≥ 87 − 35 = 19 35 , so that p (v, vi ) ≥ 35 − 20 > 0. 15 3 9 If t(v, vi ) > 0 and min{di , di+1 } = 4, then p(v, vi ) ≥ 7 − 2 · 4 = 14 and 9 1 0 0 p (v, vi ) ≥ 14 − 4 > 0. Thus, c (v) is a sum of positive summands. 4. CONCLUDING REMARK Note that besides our Theorem, it is possible to prove that χc (G) is upper bounded by max{∆∗ (G) + 3, 23} and by max{∆∗ (G) + 4, 21}. For that, an analogue of Lemma 3 and the Discharging Method with Rule 1 can be used. ACKNOWLDEGEMENTS The authors wish to thank to anonymous referees for their helpful comments, which aided to improve the presentation of the article. ON A CONJECTURE BY PLUMMER AND TOFT 189 References [1] K. Ando, H. Enomoto, and A. Saito, Contractible edges in 3-connected graphs. J Combin Theory (Ser. B) 42 (1987), 87–93. [2] K. Appel and W. Haken, Every planar map is four colorable. Contemp Math 98, American Mathematical Society, Providence, Rhode Island, 1989. [3] O.V. Borodin, Cyclic coloring of plane graphs. Discrete Math 100 (1992), 281–289. [4] O.V. Borodin, A new proof of the 6 color theorem. J Graph Theory 19 (1995), 507–521. [5] O.V. Borodin, Cyclic degree and cyclic coloring of 3-polytopes. J Graph Theory 23 (1996), 225–231. [6] O.V. Borodin, D.P. Sanders, and Y. Zhao, On cyclic colorings and their generalizations, submitted. [7] O.V. Borodin and D.R. Woodall, Cyclic colourings of 3-polytopes with large maximum face size, submitted. [8] O.V. Borodin and D.R. Woodall, Cyclic degrees of 3-polytopes, submitted. [9] H. Enomoto, M. Horňák, and S. Jendrol’, Cyclic chromatic number of 3connected plane graphs, submitted. [10] R. Halin, Zur Theorie der n-fach zusammenhängenden Graphen. Abh Math Sem Univ Hamburg 33 (1969), 133–164. [11] P.J. Heawood, Map-colour theorem. Quart J Pure Appl Math 24 (1890), 332– 338. [12] M. Horňák and S. Jendrol’, Unavoidable sets of face types for planar maps. Discussiones Math Graph Theory 16 (1996), 123–141. [13] M. Horňák and S. Jendrol’, On vertex types and cyclic colourings of 3connected plane graphs, submitted. [14] T. Jensen and B. Toft, Graph colouring problems, Wiley–Interscience, New York, 1995. [15] O. Ore and M.D. Plummer, Cyclic coloration of plane graphs. Recent progress in combinatorics (Proceedings of the Third Waterloo Conference on Combinatorics), Academic Press, New York, 1969, pp. 287–293. [16] M.D. Plummer and B. Toft, Cyclic coloration of 3-polytopes. J Graph Theory 11 (1987), 507–515.

1/--страниц