Colouring prime distance graphs

Abstract

Four colours are necessary and sufficient to colour all the integers so that any two with difference equal to a prime have different colours. We investigate the corresponding problem when the set D of prescribed differences is a proper subset of the primes. In particular, we prove that if D contains {2, 3} and also contains a pair of twin primes (one of which may be 3), then four colours are necessary. Numerous results regarding periodic colourings are also obtained. However, the problem of characterizing those sets D which necessitate four colours remains open. © 1990 Springer-Verlag.