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.