caa a22 4500 388091428 CHVBK 20180307125253.0 cr unu---uuuuu 161130e199902 xx s 000 0 eng 10.1017/S0004972700032627 doi S0004972700032627 pii (NATIONALLICENCE)cambridge-10.1017/S0004972700032627 zhu Xuding Department of Applied Mathematics, National Sun Yat-sen University, Kaohsiung, Taiwan 80424 e-mail: zhu@math.nsysu.edu.tw Circular colouring and graph homomorphism [Elektronische Daten] [Xuding zhu] For any pair of integers p, q such that (p, q) = 1 and p ≥ 2q, the graph has vertices {0, 1, ..., p − 1} and edges {ij: q ≤ |i − j| ≤ p − q}. These graphs play the same role in the study of circular chromatic number as that played by the complete graphs in the study of chromatic number. The graphs share many properties of the complete graphs. However, there are also striking differences between the graphs and the complete graphs. We shall prove in this paper that for many pairs of integers p, q, one may delete most of the edges of so that the resulting graph still has circular chromatic number p/q. To be precise, we shall prove that for any number r < 2, there exists a rational number p/q (where (p, q) = 1) which is less than r but arbitrarily close to r, such that contains a subgraph H with and . This is in sharp contrast to the fact that the complete graphs are edge critical, that is, the deletion of any edge will decrease its chromatic number and its circular chromatic number. Copyright © Australian Mathematical Society 1999 Bulletin of the Australian Mathematical Society Cambridge University Press 59/1(1999-02), 83-97 0004-9727 59:1<83 1999 59 BAZ https://doi.org/10.1017/S0004972700032627 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1017/S0004972700032627 text/html Onlinezugriff via DOI NATIONALLICENCE 100 1- zhu Xuding Department of Applied Mathematics, National Sun Yat-sen University, Kaohsiung, Taiwan 80424 e-mail: zhu@math.nsysu.edu.tw NATIONALLICENCE 773 0- Bulletin of the Australian Mathematical Society Cambridge University Press 59/1(1999-02), 83-97 0004-9727 59:1<83 1999 59 BAZ CC0 http://creativecommons.org/publicdomain/zero/1.0 nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-cambridge