Chromatic coloring of distance graphs, III

• Barnabas, George ; Yegnanarayanan, Venkataraman ^[1]
  1. [1] Kalasalingam Academy of Research and Education.
• Localización: Proyecciones: Journal of Mathematics, ISSN 0716-0917, ISSN-e 0717-6279, Vol. 42, Nº. 1, 2023, págs. 175-204
• Idioma: inglés
• DOI: 10.22199/issn.0717-6279-5689
• Enlaces
  • Texto completo
• Resumen

  • 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.

• Referencias bibliográficas
  • 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,...
  • 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,...
  • 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,...
  • 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]....
  • 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,...
  • 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....