##
**Zentralblatt MATH**

**Publications of (and about) Paul Erdös**

**Zbl.No: ** 698.05033

**Autor: ** Eggleton, R.B.; Erdös, Paul; Skilton, D.K.

**Title: ** Colouring prime distance graphs. (In English)

**Source: ** Graphs Comb. 6, No.1, 17-32 (1990).

**Review: ** 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.

**Reviewer: ** K.Engel

**Classif.: ** * 05C15 Chromatic theory of graphs and maps

11B75 Combinatorial number theory

**Keywords: ** periodic colouring; prime distance graph; chromatic number

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag