Chromatic coloring of distance graphs, III
DOI:
https://doi.org/10.22199/issn.0717-6279-5689Keywords:
chromatic number, distance graph, prime distance graph, prime, distance labeling, unit distance graphAbstract
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.
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
Published
How to Cite
Issue
Section
Copyright (c) 2023 George Barnabas, Venkataraman Yegnanarayanan
This work is licensed under a Creative Commons Attribution 4.0 International License.
-
Attribution — You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
- No additional restrictions — You may not apply legal terms or technological measures that legally restrict others from doing anything the license permits.