Distance graphs with finite chromatic number (Q1850605): Difference between revisions

Let \(D = \{ d_1, d_2, \ldots \} \) be a set of positive integers. Then the distance graph \(G(D)\) has as its vertex set the set of integers \(\mathbb{Z}\) and two vertices \(i, j\) are adjacent if and only if \( i-j \in D\). The authors show that if \(\inf\{d_{i+1}/d_i\} >1\), then the chromatic number of \(G(D)\) is finite. They also show that if \(\varepsilon_1 \geq \varepsilon_2 \geq \varepsilon_3 \geq\cdots\) is a sequence of positive reals tending to zero (arbitrarily slowly), then there is a distance set \(D = \{ d_1, d_2, \ldots \}\) where \(d _{i+1} \geq (1 + \varepsilon_i)d_i\) for all \(i = 1, 2, \ldots\) such that \(G(D)\) cannot be colored with a finite number of colors.