On a question concerning prime distance graphs
type: Item
instance of: scholarly article
title: On a question concerning prime distance graphs
zbMATH Open document ID: 1001.05052
DOI: 10.1016/S0012-365X(01)00221-7
author: V. Yegnanarayanan
published in: Discrete Mathematics
publication date: 2002-05-15T00:00:00Z
review text: 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.
reviewed by: Arnfried Kemnitz
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 1741696
zbMATH Keywords: distance graph
zbMATH Keywords: chromatic number
MaRDI profile type: Publication
full work available at URL: s0012-365x(01)00221-7
OpenAlex ID: W1992157983
Recommended article: Chromatic number of prime distance graphs
Recommended article: Colouring prime distance graphs
Recommended article: Q4285228
Recommended article: Q4005786
Recommended article: Distance Graphs Generated by Five Primes (Research)
Recommended article: Coloring of integer distance graphs
Recommended article: Integral distance graphs
Recommended article: Q5468433
Recommended article: Q5313821
Recommended article: Q3824329
description: scientific article; zbMATH DE number 1741696