×

Integral distance graphs. (English) Zbl 0878.05028

For some \(D\subset N^+\) the distance graph \(G(Z,D)\) has an edge connecting any two integers with a distance appearing in \(D\). It is proven that for finite \(D\), \(|D|+1\) is a sharp upper bound for the chromatic number of \(G(Z,D)\). This number is then determined exactly for almost all triplets \(D\).

MSC:

05C12 Distance in graphs
05C15 Coloring of graphs and hypergraphs
PDFBibTeX XMLCite
Full Text: DOI