Colouring prime distance graphs
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.
- Colouring of distance graphs
- Coloring the distance graphs
- Chromatic number of prime distance graphs
- Colorings of distance graphs
- The distance coloring of graphs
- Coloring distance graphs and graphs of diameters
- Coloring of integer distance graphs
- On distance graph coloring problems
- Coloring of n-dimensional distance graphs
- Color-distance in color-connected graphs
- On the chromatic number of circulant graphs
- Pattern periodic coloring of distance graphs
- Distance graphs and \(T\)-coloring
- Chromatic number of prime distance graphs
- On a question concerning prime distance graphs
- The chromatic numbers of distance graphs
- Coloring planar Toeplitz graphs and the stable set polytope.
- Coloring of integer distance graphs
- Asymptotic clique covering ratios of distance graphs
- Prime power and prime product distance graphs
- Circular chromatic numbers of some distance graphs
- Chromatic number of distance graphs generated by the sets \(\{2,3,x,y\}\)
- Circular chromatic numbers of distance graphs with distance sets missing multiples
- On finite prime distance graphs
- On packing colorings of distance graphs
- Distance graphs on \(\mathbb R^n\) with 1-norm
- Distance graphs with maximum chromatic number
- On uniquely k-determined permutations
- Coloring of distance graphs with intervals as distance sets
- Minimum chromaticity of circulant graphs
- Study of $$\kappa (D)$$ for $$D = \{2, 3, x, y\}$$
- Connectivity and diameter in distance graphs
- scientific article; zbMATH DE number 4099328 (Why is no real title available?)
- Finite prime distance graphs and 2-odd graphs
- scientific article; zbMATH DE number 528072 (Why is no real title available?)
- Distance Graphs Generated by Five Primes (Research)
- Powers of cycles, powers of paths, and distance graphs
- On Hamiltonian paths in distance graphs
- Graph colourings and partitions
- Coloring distance graphs on the plane
- Chromatic number of a line with geometric progressions of forbidden distances and the complexity of recognizing distance graphs
- Chromatic coloring of distance graphs, III
- Chromatic coloring of distance graphs \(\mathrm{V}\)
- A note on prime distance graphs with chromatic number 3 or 4
- Long cycles and paths in distance graphs
- Prime and polynomial distances in colourings of the plane
- On the independence ratio of distance graphs
- The vertex linear arboricity of distance graphs
- Fractional chromatic number of distance graphs generated by two-interval sets
- Invisible runners in finite fields
This page was built for publication: Colouring prime distance graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q912118)
