The chromatic numbers of distance graphs (Q1356742): Difference between revisions

Let \({\mathcal Z}\) be the set of all integers. For a subset \(D\) of \({\mathcal Z}\), the distance graph \(G({\mathcal Z}, D)\) is the graph with vertex set \({\mathcal Z}\) in which two vertices \(x\), \(y\) are adjacent if \(|x-y |\in D\). The chromatic number \(\chi (G ({\mathcal Z}, D)) =2\) of the distance graph is connected with a well-known plane coloring problem: What is the least number of colors which can be used to color all points of Euclidean plane so that no two vertices at unit distance are colored the same? In the unpublished paper [\textit{Chang} et al., Integral distance graphs (1995)], the following conjecture was proposed. Suppose \(D= \{a,b,c\}\), where \(0<a <b<c\) are integers. Then \(\chi (G ({\mathcal Z},D)) =4\) if and only if either \(c=a+b\) and \(a\not \equiv b \pmod 3\) or \(a=1\), \(b=2\), and \(c \equiv 0 \pmod 3\). In the paper under review the authors give some partial results on \(\chi(G ({\mathcal Z},D))\) with \(|D|=3\) which support the above conjecture. In particular, they present a complete classification of those \(D= \{a,b,c\}\) for which \(b\) is a multiple of \(a\) and \(\chi (G({\mathcal Z}, D))=3\).