Distance graphs and T-coloring

Abstract

We discuss relationships among T-colorings of graphs and chromatic numbers, fractional chromatic numbers, and circular chromatic numbers of distance graphs. We first prove that for any finite integral set T that contains 0, the asymptotic T-coloring ratio R(T) is equal to the fractional chromatic number of the distance graph G(Z, D), where D = T-{0}. This fact is then used to study the distance graphs with distance sets of the form D-m,D- k = {1, 2, ..., m}- {k}. The chromatic numbers and the fractional chromatic numbers of G(Z, D-m,D- k) are determined for all values of m and k. Furthermore, circular chromatic numbers of G(Z, D-m,D- k) fur some special values of m and k are obtained. (C) 1999 Academic Press.