Distance graphs with finite chromatic number (Q1850605): Difference between revisions
From MaRDI portal
ReferenceBot (talk | contribs) Changed an Item |
Normalize DOI. |
||
Property / DOI | |||
Property / DOI: 10.1006/jctb.2001.2093 / rank | |||
Property / DOI | |||
Property / DOI: 10.1006/JCTB.2001.2093 / rank | |||
Normal rank |
Latest revision as of 10:29, 16 December 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Distance graphs with finite chromatic number |
scientific article |
Statements
Distance graphs with finite chromatic number (English)
0 references
10 December 2002
0 references
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.
0 references