×

Distance graphs with finite chromatic number. (English) Zbl 1027.05036

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.

MSC:

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

References:

[1] Chen, Y. G.; Cusick, T. W., The view-obstruction problem for \(n\)-dimensional cubes, J. Number Theory, 74, 126-133 (1999) · Zbl 0921.11030
[2] Eggleton, R. B.; Erdős, P.; Skilton, D. K., Coloring the real line, J. Combin. Theory B, 39, 86-100 (1985) · Zbl 0549.05029
[3] Wills, J. M., Zwei Sätze ��ber inhomogene diophantische Approximation von Irrationalzahlen, Monatsch. Math., 71, 263-269 (1967) · Zbl 0148.27505
[4] Zhu, X., Pattern periodic coloring of distance graphs, J. Combin. Theory B, 73, 195-206 (1998) · Zbl 0904.05028
[5] X. Zhu, The circular chromatic number of distance graphs with distance sets of cardinality 3, in press.; X. Zhu, The circular chromatic number of distance graphs with distance sets of cardinality 3, in press. · Zbl 1012.05071
[6] Voigt, M., On the chromatic number of distance graphs, J. Inform. Process. Cybernet. EIK, 28, 21-28 (1992) · Zbl 0751.05044
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.