close

Вход

Забыли?

вход по аккаунту

?

416

код для вставкиСкачать
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.
Документ
Категория
Без категории
Просмотров
3
Размер файла
175 Кб
Теги
416
1/--страниц
Пожаловаться на содержимое документа