# Chromatic coloring of distance graphs, III

## Authors

• George Barnabas Kalasalingam Academy of Research and Education.
• Venkataraman Yegnanarayanan Kalasalingam Academy of Research and Education.

## Keywords:

chromatic number, distance graph, prime distance graph, prime, distance labeling, unit distance graph

## Abstract

A graph G(Z, D) with vertex set Z is called an integer distance graph if its edge set is obtained by joining two elements of Z by an edge whenever their absolute difference is a member of D. When D = P or D ⊆ P where P is the set of all prime numbers then we call it a prime distance graph. After establishing the chromatic number of G(Z, P ) as four, Eggleton has classified the collection of graphs as belonging to class i if the chromatic number of G(Z, D) is i. The problem of characterizing the family of graphs belonging to class i when D is of any given size is open for the past few decades. As coloring a prime distance graph is equivalent to producing a prime distance labeling for vertices of G, we have succeeded in giving a prime distance labeling for certain class of all graphs considered here. We have proved that if D = {2, 3, 5, 7, 7th prime, 10th prime, 13th prime, 16th prime, (7 + j)th  prime, ..., (4 + j)th  prime for any s ∈ N}, then there exists a prime distance graph with distance set D in class 4 and if D = {2, 3, 5, 4th prime, 6th prime, 8th prime, (4 + j)th  prime, ..., (2 + j)th   prime for any s ∈ N} then there exists a prime distance graphs with distance set D in class 3. Further, we have also obtained some more interesting results that are either general or existential such as a) If D is a specific sequence of integers in arithmetic progression then there exist a prime distance graph with distance set D, b) If G is any prime distance graph in class i for 1 ≤ i ≤ 4 then G × K2 is also a prime distance graph in the respective class i, c) A countable union of disjoint copies of prime distance graph is again a prime distance graph, d) The Middle/Total graph of a path on n vertices is a prime distance graph. In addition we also provide a new different proof for establishing a fact that all cycles are prime distance graph.

## Author Biographies

### George Barnabas, Kalasalingam Academy of Research and Education.

Department of Mathematics.

### Venkataraman Yegnanarayanan, Kalasalingam Academy of Research and Education.

Department of Mathematics.

## References

A. Soifer, The Mathematical coloring book. Springer, 2009.

A. D. N. J. de Grey, “The Chromatic number of the plane is at least 5”, Geombinatorics, vol. 28, no. 1, pp. 18-31, 2018. https://doi.org/10.48550/arXiv.1804.02385

M. J. H. Heule, “Computing small unit distance graph with chromatic number 5”, Geombinatorics, vol. 28, no. 1, pp. 32-50, 2018. https://doi.org/10.48550/arXiv.1805.12181

P. D. Johnson, Euclidean distance graph on rational points. Birkhauser: Springer, 2010.

P. D. Johnson, “Introduction to ‘Colorings of metric spaces’ by Benda and Perles”, Geombinatorics, 9(3), pp. 110-112, 2000.

R. B. Eggleton, P. Erdös, D. K. Skilton, “Colouring the real line”, Journal of Combinatorial Theory, Series B, vol. 39, no. 1, pp. 86-100, 1985. https://doi.org/10.1016/0095-8956(85)90039-5

R. B. Eggleton, P. Erdös, D. K. Skilton, “Erratum”, Journal of Combinatorial Theory, Series B, vol. 41 (1), p. 139, 1986. https://doi.org/10.1016/0095-8956(86)90032-8

Y. Katznelson, “Chromatic numbers of Cayley graph on Z and recurrence”, Combinatorica, vol. 21, pp. 211-219, 2001. https://doi.org/10.1007/s004930100019

Zs. Tuza, M. Voigt and I. Z Ruzza, “Distance graph with finite Chromatic number”, Journal of Combinatorics and Theory, Series B, vol. 85, pp. 181-187, 2002. [On line]. Available: https://bit.ly/3CI57OI

J. Grytczuk and S. Ferhangi, “Distance Graph and Arithmetic Progressions”, INTEGERS, vol. A, no. 11, 2021. [On line]. Available: https://bit.ly/3w7f309

X. Zhu, “Circular chromatic number of distance graphs with distance sets of cardinality 3”, Journal of Graph Theory, vol. 41, pp. 195-207, 2002. https://doi.org/10.1002/jgt.10062

A. Kemnitz and M. Marangio, “Colorings and list colorings of integers distance graphs”, Congress Number, vol. 151, pp. 75-84, 2001.

A. Kemnitz and M. Marangio, “Chromatic numbers of integer distance graphs”, Discrete Mathematics, vol. 233, pp. 239-246, 2001. [On line]. Available: https://bit.ly/3XvOVbk

P. Erdös, D. K. Skilton, R. B. Eggleton, “Colouring the real line”, Journal of Combinatorial Theory, Series B, vol. 39, no. 1, pp. 86-100, 1985. https://doi.org/10.1016/0095-8956(85)90039-5

P. Erdös, D. K. Skilton, R. B. Eggleton, “Colouring prime distance graphs”, Graphs and Combinatorics, vol. 6, pp. 17-32, 1990. https://doi.org/10.1007/bf01787476

J. D. Laison, C. Starr and A. Halker, Finite Prime Distance Graphs and 2-odd Graphs, 2021. https://doi.org/10.48550/arXiv.2106.02177

V. Yegnanarayanan, “Chromatic number of graphs with special distance sets, I”, Algebra and Discrete Mathematics, vol. 17, pp. 135-160, 2014.

V. Yegnanarayanan, “On a question concerning prime distance graphs”, Discrete Mathematics, vol. 245, no. 1-3, pp. 293-298, 2002. https://doi.org/10.1016/S0012-365X(01)00221-7

V. Yegnanarayanan, G. N. Yegnanarayanan and M. M. Balus, “On Coloring Catalan Number Distance Graphs and Interference Graph”, Symmetry, vol. 10, no. 468, pp. 1-13, 2018. https://doi.org/10.3390/sym10100468

2023-01-26

## How to Cite


G. . Barnabas and V. Yegnanarayanan, “Chromatic coloring of distance graphs, III”, Proyecciones (Antofagasta, On line), vol. 42, no. 1, pp. 175-204, Jan. 2023.

Artículos