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