Circular chromatic numbers of distance graphs with distance sets missing multiples

Abstract

Given positive integers m, k, s with m > sk, let D-m,D-k,D-s represent the set {1, 2,..., m} {k, 2k,..., sk}. The distance graph G(Z, D-m,D-k,D-s) has as vertex set all integers Z and edges connecting i and j whenever i - j is an element of D-m,D-k,D-s. This paper investigates chromatic numbers and circular chromatic numbers of the distance graphs G(Z, D-m,D-k,D-s). Deuber and Zhu [8] and Liu [13] have shown that [m+sk+1/s+1] less than or equal to chi(G(Z, D-m,D-k,D-s)) less than or equal to [m+sk+1/s+1] + 1 when m greater than or equal to (s + 1)k. In this paper, by establishing bounds for the circular chromatic number chi(C)(G(Z, D-m,D-k,D-s)) of G(Z, D-m,D-k,D-s), we determine the values of chi(G(Z, D-m,D-k,D-s)) for all positive integers m, k, s and chi(C)(G(Z, D-m,D-k,D-s)) for some positive integers m, k, s. (C) 2000 Academic Press.