Fractional chromatic number and circular chromatic number for distance graphs with large clique size

摘要

Let M be a set of positive integers. The distance graph generated, by M, denoted by G(Z,M), has the set Z of all integers as the vertex set, and edges ij whenever i - j is an element of M. We investigate the fractional chromatic number and the circular chromatic number for distance graphs, and discuss their close connections with some number theory problems. In particular, we determine the fractional chromatic number and the circular chromatic number for all distance graphs G(Z,M) with clique size at least M, except for one case of such graphs. For the exceptional case, a lower bound for the fractional chromatic number and an upper bound for the circular chromatic number are presented; these bounds are sharp enough to determine the chromatic number for such graphs. Our results confirm a conjecture of Rabinowitz and Proulx [22] on the density of integral sets with missing differences, and generalize some known results on the circular chromatic number of distance graphs and the parameter involved in the Wills' conjecture [26] (also known as the "lonely runner conjecture" [1]). (C) 2004 Wiley Periodicals, Inc.