Integral distance graphs

Abstract

Suppose D is a subset of all positive integers. The distance graph G(Z, D) with distance set D is the graph with vertex set Z, and two vertices x and y are adjacent if and only if \x - y\ is an element of D. This paper studies the chromatic number chi(Z, D) of G(Z, D). In particular, we prove that chi(Z,D) less than or equal to \D\ + 1 when \D\ is finite. Exact values of chi(G, D) are also determined for some D with \D\ = 3. (C) 1997 John Wiley & Sons, Inc.