Colouring prime distance graphs (Q912118): Difference between revisions

Let \(D\) be a set of prime numbers. The prime distance graph \(Z(D)\) is the graph with integers as vertex set, and an edge between \(x\) and \(y\) precisely when \(|x-y| \in D\). Easily one obtains for the chromatic number \(\chi(D)\) of \(Z(D)\) that \(\chi(D) \leq 4\). By previous work of the authors \(\chi(D)\) is known when \(|D| \leq 3\), and the sets \(D\) with \(\chi(D)=1\) or 2 are classified. The paper under review is a contribution to the ``Four Colour Problem for Prime Numbers'': Characterize the sets D with \(\chi(D)=4\). We mention here only some results of the paper: 1) If \(p\) and \(p+2\) are any twin primes, then \(\chi(\{2,3,p,p+2\})=4.\) 2) If \(D\) is finite then \(Z(D)\) has a periodic proper colouring using only \(\chi(D)\) colours (several theorems concerning the smallest such period are given, and by means of a computer these periods are calculated for many examples). 3) There are finite sets \(D\) for which there exists aperiodic proper colourings using only \(\chi(D)\) colours.