On a question concerning prime distance graphs
An integer distance graph is a graph \(G(D)\) with the set of integers as vertex set and with an edge joining two vertices \(u\) and \(v\) if and only if \(|u-v|\in D\) where \(D\) is a subset of the set of positive integers. If \(D\) is a subset of the set \(P\) of primes then \(G(D)\) is called prime distance graph. Since \(\chi (G(D))=4\) if \(D=\{2,3,5\}\) or \(D=P\) where \(\chi (G(D))\) is the chromatic number of \(G(D)\) \textit{R. B. Eggleton} et al. [Discrete Math. 69, 105 (1988)] posed the problem to characterize all sets \(D\) of primes with: If \(|D|=4\), then, if and only if \(\{2,3,5\} \subset D\), \(D=\{2,3,p,p+2\}\) or \(D\) is one of eight particular cases. Therefore, \textit{A. Kemnitz} and \textit{H. Kolberg} [Discrete Math. 191, 113-123 (1998; Zbl 0956.05044)] raised the question: Is there, for every fixed cardinal, only a finite collection of minimum sets \(D \subset P\) of the given size (i.e. no proper subset of \(D\) has chromatic number 4) for which \(D\) is without twin primes and \(\chi (G(D))=4\)? The main result of this note is: If Schinzel's conjecture on irreducible polynomials is true then there exist infinitely many such \(D\) of cardinality 5.
scientific article; zbMATH DE number 1741696