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

Books Problems Set Theory Combinatorics Extremal Probl/Ramsey Th.
Graph Theory Add.Number Theory Mult.Number Theory Analysis Geometry
Probabability Personalia About Paul Erdös Publication Year Home Page