close

Вход

Забыли?

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

?

400

код для вставкиСкачать
A Simple Proof of Moser?s
Theorem
Xuding Zhu
DEPARTMENT OF APPLIED MATHEMATICS
NATIONAL SUN YAT?SEN UNIVERSITY
KAOHSIUNG, TAIWAN 80424
Email: zhu@math.nsysu.edu.tw
Received March 7, 1997; revised July 27, 1998
Abstract: This article gives a simple proof of a result of Moser, which says that,
for any rational number r between 2 and 3, there exists a planar graph G whose
c 1999 John Wiley & Sons, Inc. J Graph Theory 30:
circular chromatic number is equal to r . 19?26, 1999
Keywords: circular chromatic number, planar graphs, Farey sequence
1. INTRODUCTION
The circular chromatic number ?c (G) of a graph G, introduced by Vince in 1988
(under the name ??the star-chromatic number??), is a natural generalization of the
chromatic number of a graph.
For a pair of integers k, d, a (k, d)-coloring of a graph G is a mapping c of
V (G) to the set {0, 1, . . . , k ? 1} such that, for any adjacent vertices x, y of G, d ?
|c(x) ? c(y)| ? k ? d. The circular chromatic number ?c (G) of a graph G is the
infimum of the ratios k/d for which there exists a (k, d)-coloring of G.
It is known (cf. [5]) that, for any rational number r ? 2, there exists a graph G with
?c (G) = r. However, the question remains open whether or not for every rational
number r between 2 and 4 there is a planar graph G with ?c (G) = r. Recently,
with a brilliant construction and a complex argument, Moser [4] proved that, for
every rational number r between 2 and 3, there does exist a planar graph G with
Contract grant sponsor: National Science Council
Contract grant no.: NSC87-2115-M-110-004.
c
1999 John Wiley & Sons, Inc.
CCC 0364-9024/99/010019-08
20 JOURNAL OF GRAPH THEORY
?c (G) = r. This article gives a simple proof of Moser?s result. The construction
of the graphs is the same as in [4], and the idea of using the Farey sequence and
the definition of the alpha sequence of a fraction are also the same as in [4]. The
different part is in the proof that determines the circular chromatic number of the
constructed graphs.
2. PRELIMINARY RESULTS
Given any rational number p/q between 2 and 3 such that (p, q) = 1, we let p0 , q 0
be the unique positive integers such that p0 < p, q 0 < q , and pq 0 ? qp0 = 1. Then
it is straightforward to verify that p0 /q 0 < p/q and that p0 /q 0 is the largest fraction
with the property that p0 /q 0 < p/q and p0 ? p. Similarly, we let p00 , q 00 be positive
integers such that p00 < p0 , q 00 < q 0 and p0 q 00 ? p00 q 0 = 1. Repeating this process
of finding smaller and smaller fractions, we shall reach the fraction 2/1 in a finite
number of steps. Thus, given any rational p/q between 2 and 3, there corresponds
a unique sequence of fractions
p0
2
p1
p2
pn
p
=
<
<
< иии <
= .
1
q0
q1
q2
qn
q
The sequence (pi /qi : i = 0, 1, . . . , n) is called the Farey sequence of p/q (cf. [4]).
It will also be convenient to define p?1 = ?1 and q?1 = 0.
As pi qi?1 ? pi?1 qi = 1 and pi?1 qi?2 ? pi?2 qi?1 = 1, it follows that pi?1 (qi +
qi?2 ) = qi?1 (pi + pi?2 ). As pi?1 , qi?1 are co-prime, for i ? 1,
?i =
pi + pi?2
qi + qi?2
=
pi?1
qi?1
is an integer, which is greater than 1, and hence is at least 2. The sequence
(?1 , ?2 , . . . , ?n ) is called the alpha sequence of p/q (cf. [4]), which is obviously
uniquely determined by p/q . The process of deducing the alpha sequence from the
rational p/q can also be reversed. In other words, each sequence (?1 , ?2 , . . . , ?n )
with ?i ? 2 determines a rational p/q between 2 and 3. Indeed, given the alpha
sequence (?1 , ?2 , . . . , ?n ), the fractions pi /qi can be easily determined by solving
the difference equations
pi = ?i pi?1 ? pi?2 , qi = ?i qi?1 ? qi?2 ,
(?)
with the initial condition that (p?1 , q?1 ) = (?1, 0) and (p0 , q0 ) = (2, 1).
By repeatedly applying the equation (?), we may express pi (respectively, qi ) in
terms of pi?t and pi?t?1 (respectively, qi?t and qi?t?1 ) for any 2 ? t ? i. Lemma
SIMPLE PROOF OF MOSER?S THEOREM 21
2.1 below gives the explicit expressions. For 1 ? r ? s ? n, we let
?
?r,s
Lemma 2.1.
?
?
?
?
= det ?
?
?
?
?
?r
1
0
1
1 ?r+1
0
1
?r+2
..
..
..
.
.
.
0
0
0
0
0
0
иии
иии
иии
..
.
0
0
0
..
.
0
0
0
..
.
?
?
?
?
?
?.
?
?
?
1 ?
и и и ?s?1
и и и 1 ?s
For 2 ? t ? i, we have
pi = pi?t ?i?t+1,i ? pi?t?1 ?i?t+2,i , qi = qi?t ?i?t+1,i ? qi?t?1 ?i?t+2,i . (??)
Proof. It suffices to prove the first equality. We shall prove it by induction on t.
When t = 2, by applying (?) twice, we obtain (??). Suppose that i ? t > 2, and
that (??) is true for any t0 < t. Then by cofactor expansion,
pi?t ?i?t+1,i ? pi?t?1 ?i?t+2,i = ?i (pi?t ?i?t+1,i?1 ? pi?t?1 ?i?t+2,i?1 )
? (pi?t ?i?t+1,i?2 ? pi?t?1 ?i?t+2,i?2 )
= ?i pi?1 ? pi?2 = pi .
The second equality uses the induction hypothesis.
By letting t = i in (??), and by using the initial condition, we have
pi = 2?1,i + ?2,i , qi = ?1,i .
Lemma 2.2.
(? ? ?)
For 2 ? t ? i, pi?t qi = pi qi?t ? ?i?t+2,i .
Proof. We prove it by induction on t. The case t = 2 is proved by applying
twice the equality (?). Assume t > 2 and that the lemma is true for t ? 1, i.e.,
pi?t+1 qi = pi qi?t+1 ? ?i?t+3,i . Since pi?t qi?t+1 = pi?t+1 qi?t ? 1, we have
(pi?t+1 qi?t ? 1)qi
qi?t+1
qi + qi?t ?i?t+3,i
= pi qi?t ?
qi?t+1
= pi qi?t ? ?i?t+2,i .
pi?t qi =
The second equality uses the induction hypothesis, and the last equality follows
from (??).
Lemma 2.3.
For any 2 < t ? i, ?t,i ? ?t?1,i .
We omit the proof, which is an induction, by noting that ?j ? 2.
Lemma 2.4 below was proved in [2] and also implicitly used in [5, 6]. Given a
(k, d)-coloring c of a graph G, we define a directed graph Dc (G) on the vertex set
of G by putting a directed edge from x to y if and only if (x, y) is an edge of G and
that c(x) ? c(y) = d(mod k).
22 JOURNAL OF GRAPH THEORY
Lemma 2.4. For any graph G, ?c (G) = k/d if and only if G is (k, d)-colorable,
and for any (k, d)-coloring c of G, the directed graph Dc (G) contains a directed
cycle.
A simple calculation shows that the length of the directed cycle in Dc (G) is a
multiple of k , and, hence, is at least k (under the assumption that (k, d) = 1). Thus,
we have the following corollary.
Corollary 2.1. For any graph G, if ?c (G) = k/d, where (k, d) = 1, then G has
a cycle of length at least k. In particular k ? |V (G)|.
3. CONSTRUCTION AND PROOF
Let r = p/q be any rational number between 2 and 3, where (p, q) = 1, and let
(?1 , ?2 , . . . , ?n ) be the alpha sequence of p/q , and let (pi /qi : i = 1, 2, . . . , n) be
the Farey sequence of p/q .
We construct graphs Fi , Hi (for i = 1, 2, . . . , n) recursively as follows.
F1 is a singleton, which is labeled with two labels u1 , v1 ; H1 is a path with 2?1
vertices in which the two end vertices are labeled x1 , y1 , respectively. F2 is a path
with 2?1 ? 2 vertices whose two end vertices are labeled u2 , v2 , respectively.
For i ? 2, the graph Hi is constructed as follows. Take ?i copies of Fi?1 , in
j
. Also take
which the labeled vertices in the j th copy are labeled with uji?1 and vi?1
?i ? 1 copies of Hi?1 , in which the labeled vertices in the j th copy are labeled with
j
xji?1 and yi?1
. Then Hi is obtained from these copies of Hi?1 and Fi?1 by joining
j
j
j
j+1
xi?1 to both uji?1 and uj+1
i?1 , and joining yi?1 to both vi?1 and vi?1 . Also label the
?i
with additional label yi .
vertex u1i?1 with the additional label xi , and label vi?1
For i ? 3, the graph Fi is constructed as follows. Take ?i?1 ? 1 copies of Fi?2 ,
j
in which the labeled vertices in the j th copy are labeled with uji?2 and vi?2
. Take
?i?1 ? 2 copies of Hi?2 , in which the labeled vertices in the j th copy are labeled
j
. Then Fi is obtained from these copies of Hi?1 and Fi?1 by
with xji?2 and yi?2
j
j
j+1
joining xji?2 to both uji?2 and uj+1
i?2 , and joining yi?2 to both vi?2 and vi?2 . Also
?i?1 ?1
label the vertex u1i?2 with the additional label ui , and label vi?2
with additional
label vi .
Finally, let Gi be obtained from a copy of Fi and a copy of Hi by joining xi to
ui , and yi to vi . Figure 1 illustrates the construction of Fi , Hi , and Gi .
It follows from the construction that the graphs Gi are planar. We shall show that
?c (Gi ) = pi /qi .
For i ? 1, let fi = |Fi |, hi = |Hi | and gi = |Gi |. It follows from the construction
that
gi = fi + hi , f1 = 1, f2 = 2?1 ? 2, h1 = 2?1 ,
and for i ? 2,
hi = ?i fi?1 + (?i ? 1)hi?1 ,
SIMPLE PROOF OF MOSER?S THEOREM 23
FIGURE 1. Construction of Fi , Hi and Gi
for i ? 3,
fi = (?i?1 ? 1)fi?2 + (?i?1 ? 2)hi?2 .
Simple algebraic calculation shows that
hi = ?i gi?1 ? hi?1 , fi = (?i?1 ? 1)gi?2 ? hi?2 = hi?1 ? gi?2 .
Hence,
gi = ?i gi?1 ? gi?2 .
Since g1 = p1 , g2 = p2 , and gi , pi satisfy the same difference equation, we conclude
that |Gi | = gi = pi .
Now we observe that Gi has a unique Hamiltonian cycle, up to an isomorphism.
Indeed, it is not difficult to see (or verify by induction) that each graph Fi has a
unique Hamiltonian path from ui to vi , up to an isomorphism. Also each Hi has
a unique Hamiltonian path from xi to yi , up to an isomorphism. Hence, Gi has
a unique Hamiltonian cycle, up to an isomorphism. A Hamiltonian cycle of Gi
consists of the two edges (xi , ui ) and (yi , vi ), and a Hamiltonian path of Fi from ui
to vi , and a Hamiltonian path of Hi from xi to yi (see Fig. 1). Thus, any Hamiltonian
24 JOURNAL OF GRAPH THEORY
cycle Q of Gi is of the form
(xi , ui , . . . , [fi ? 2], . . . , vi , yi , . . . , [hi ? 2], . . . , xi ).
The above notation means that there are fi ? 2 vertices between ui and vi , and
hi ? 2 vertices between yi and xi .
Lemma 3.1.
Let Q = (c1 , c2 , . . . , cpi , c1 ) be a Hamiltonian cycle of Gi . If
(ca , cb ) is an edge of Gi that is not an edge of the Hamiltonian cycle Q, then
|a ? b| = pt ? 1 or pi ? (pt ? 1) for some 1 ? t ? i ? 1.
We shall omit the proof, which is an easy induction and also quite obvious by
referring to Fig. 1.
Suppose that ?c (Gi ) = pi /qi , and that c is an (pi , qi )-coloring of Gi . It follows from Lemma 2.4 that there is a directed cycle of Dc (Gi ) of length at least
pi . Since |Gi | = pi , we conclude that there is a Hamiltonian cycle, say Q =
(c1 , c2 , . . . , cpi , c1 ), of Gi such that c(cj ) ? c(cj?1 ) = qi (mod pi ). Therefore, if we
know the ??distance?? between two vertices x, y along the positive direction of the
cycle Q, then the color of x determines the color of y , and the color of y determines
the color of x.
Lemma 3.2. Suppose that ?c (Gi ) = pi /qi for some i. Let c be any (pi , qi )coloring of Gi . Then the colors of the two vertices xi , yi uniquely determine the
colors of ui , vi . Conversely, the colors of ui , vi uniquely determine the colors of
xi , yi .
Proof. Let Q = (c1 , c2 , . . . , cpi , c1 ) be the Hamiltonian cycle of Gi such that
c(cj ) ? c(cj?1 ) = qi (mod pi ) for j = 1, 2, . . . , pi . As we noted before, the undirected Q (i.e., forgetting the direction of the edges of Q) is of the form
(xi , ui , . . . , [fi ? 2], . . . , vi , yi , . . . , [hi ? 2], . . . , xi ).
Thus, if we know the colors of xi , yi , then the direction of the cycle Q is determined,
and, hence, the colors of ui , vi are determined. Conversely, the colors of ui , vi
determine the colors of xi , yi .
Let Ti be the graph obtained from Fi and Fi?1 by connecting ui to ui?1 and vi
to vi?1 . We shall prove the following theorem by induction.
Theorem 3.1.
For each i, ?c (Gi ) = pi /qi and ?c (Ti ) > pi?1 /qi?1 .
Proof. First we shall show that ?c (Gi ) ? pi /qi . Let Q = (c1 , c2 , . . . , cpi , c1 ) be
a Hamiltonian cycle of Gi . We color the vertex ca by color ?(ca ) ? aqi (mod pi ).
Now we shall show that ? is indeed a (pi , qi )-coloring of Gi . In other words, we
shall show that for each edge (ca , cb ) of Gi , qi ? |?(ca ) ? ?(cb )| ? pi ? qi . This is
trivially true if a ? b = ▒1. Otherwise a ? b = pi?t ? 1(mod pi ) for some 1 ? t ?
i ? 1, by Lemma 3.1. Then |?(ca ) ? ?(cb )| ? (pi?t ? 1)qi (mod pi ). By applying
Lemma 2.2, we have pi?t qi ? pi ? ?i?t+2,i (mod pi ). Since pi = 2qi + ?2,i (cf.
(? ? ?)), and ?j,i ? ?2,i (cf. Lemma 2.3), we conclude that qi ? |?(ca ) ? ?(cb )| =
SIMPLE PROOF OF MOSER?S THEOREM 25
pi ? qi ? ?i?t+2,i ? pi ? qi . Therefore, ? is a (pi , qi )-coloring of Gi , and, hence,
?c (Gi ) ? pi /qi .
Next we shall prove by induction on i that ?c (Gi ) = pi /qi and ?c (Ti ) >
pi?1 /qi?1 . For i = 1, this is trivially true. Suppose that ?c (Gi ) = pi /qi and
?c (Ti ) > pi?1 /qi?1 . We consider the graphs Gi+1 and Ti+1 .
First we show that ?c (Ti+1 ) > pi /qi . If i = 2, this is trivially true. Thus,
we assume that i ? 2. Assume to the contrary that ?c (Ti+1 ) ? pi /qi . Since
|Fi+1 | < |Hi |, we have |Ti+1 | < |Gi | = pi . It follows from Corollary 2.1 that
?c (Ti+1 ) = m/w < pi /qi for some integers m, w with m < pi . As pi?1 /qi?1 is
the largest fraction satisfying the property that pi?1 < pi and pi?1 /qi?1 < pi /qi ,
we conclude that ?c (Ti+1 ) ? pi?1 /qi?1 .
We consider two cases.
Case 1: ?i = 2. In this case, Fi+1 = Fi?1 , and, hence, Ti+1 = Ti . By induction
hypothesis, ?c (Ti ) > pi?1 /qi?1 , which is a contradiction.
Case 2: ?i > 2. In this case Fi+1 consists of ?i ? 1 copies of Fi?1 , say
?i ?2
1 , . . . , F ?i ?1 , and ? ? 2 copies of H
1
Fi?1
i
i?1 , say Hi?1 , . . . , Hi?1 . For each 1 ?
i?1
j
j
? Hi?1
and
j ? ?i ? 2, each of the two subgraphs induced by the sets Fi?1
j
j+1
Hi?1 ?Fi?1 is a copy of Gi?1 . By the induction hypothesis, ?c (Gi?1 ) = pi?1 /qi?1 .
Therefore, ?c (Ti+1 ) = pi?1 /qi?1 .
j
j
? Hi?1
Let ? be a (pi?1 , qi?1 )-coloring of Ti+1 . The restriction of ? to Fi?1
j
j+1
and Hi?1 ? Fi?1 are (pi?1 , qi?1 )-colorings of Gi?1 . By Lemma 3.2, the colors of
1
1
2 .
x1i?1 , yi?1
determine the colors of u1i?1 , vi?1
as well as the colors of u2i?1 , vi?1
1 , v2
Therefore, u1i?1 , u2i?1 have the same color, and vi?1
i?1 have the same color.
?i ?1
Repeating the same argument, we conclude that u1i?1 and ui?1
have the same
?i ?1
1
1 ?F
color, and vi?1 and vi?1 have the same color. Thus, the restriction of ? to Fi?1
i
is indeed a (pi?1 , qi?1 )-coloring of Ti , contrary to the induction hypothesis. (Note
1 ? F is isomorphic to T ? e,
that the subgraph of Ti+1 induced by the subset Fi?1
i
i
where e = (vi?1 , vi ).) This completes the proof that ?c (Ti+1 ) > pi /qi .
Finally, we show that ?c (Gi+1 ) = pi+1 /qi+1 . Assume to the contrary that
?c (Gi+1 ) < pi+1 /qi+1 . Then ?c (Gi+1 ) ? pi /qi , because pi /qi is the largest
fraction that is smaller than pi+1 /qi+1 and whose enumerator is not bigger than
|Gi+1 |.
?
Now Hi+1 consists of ?i+1 copies of Fi , say Fi1 , . . . , Fi i+1 , and ?i+1 ? 1
?
?1
copies of Hi , say Hi1 , . . . , Hi i+1 . For each 1 ? j ? ?i+1 ? 1, each of the two
subgraphs induced by the sets Fij ? Hij and Hij ? Fij+1 is a copy of Gi . By the
induction hypothesis, ?c (Gi ) = pi /qi . Therefore, ?c (Gi+1 ) = pi /qi . Let ? be a
(pi , qi )-coloring of Gi+1 . The restriction of ? to Fij ?Hij and Hij ?Fij+1 are (pi , qi )colorings of Gi . With the same argument as in the second previous paragraph, we
may conclude that the restriction of ? to Fi1 ? Fi+1 is a (pi , qi )-coloring of Ti+1 ,
contrary to the previous result.
Remark. The argument in this article has been extended by the author in [7] to
prove that for every rational number r between 3 and 4, there is a planar graph G
with ?c (G) = r. Some related questions are studied or asked in [3, 7, 8].
26 JOURNAL OF GRAPH THEORY
References
[1] J. A. Bondy and P. Hell, A note on the star chromatic number, J Graph Theory
14 (1990), 479?482.
[2] D. R. Guichard, Acyclic graph coloring and the complexity of the star chromatic number, J Graph Theory 17 (1993), 129?134.
[3] P. Hell and X. Zhu, Circular chromatic number of series-parallel graphs,
(1998), to appear.
[4] D. Moser, The star-chromatic number of planar graphs, J Graph Theory 24
(1997), 33?43.
[5] A. Vince, Star chromatic number, J Graph Theory 12 (1988), 551?559.
[6] X. Zhu, Star chromatic numbers and products of graphs, J Graph Theory 16
(1992), 557?569.
[7] X. Zhu, Planar graphs with circular chromatic numbers between 3 and 4
(1997), to appear.
[8] X. Zhu, Circular chromatic number, a survey (1997), to appear.
Документ
Категория
Без категории
Просмотров
7
Размер файла
243 Кб
Теги
400
1/--страниц
Пожаловаться на содержимое документа