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.

1/--страниц