
doi: 10.1007/bf01787476
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.
prime distance graph, Coloring of graphs and hypergraphs, chromatic number, Other combinatorial number theory, periodic colouring
prime distance graph, Coloring of graphs and hypergraphs, chromatic number, Other combinatorial number theory, periodic colouring
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 41 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
