Chromatic Number of Graphs with Special Distance Sets-V

DOI: 10.4236/ojdm.2013.31001   PDF   HTML   XML   3,349 Downloads   6,265 Views   Citations

Abstract

An integer distance graph is a graph G(Z,D) with the set of integers as vertex set and an edge joining two vertices u and v if and only if u - vD where D is a subset of the positive integers. It is known that x(G(Z,D) )=4 where P is a set of Prime numbers. So we can allocate the subsets D of P to four classes, accordingly as is 1 or 2 or 3 or 4. In this paper we have considered the open problem of characterizing class three and class four sets when the distance set D is not only a subset of primes P but also a special class of primes like Additive primes, Deletable primes, Wedderburn-Etherington Number primes, Euclid-Mullin sequence primes, Motzkin primes, Catalan primes, Schroder primes, Non-generous primes, Pell primes, Primeval primes, Primes of Binary Quadratic Form, Smarandache-Wellin primes, and Highly Cototient number primes. We also have indicated the membership of a number of special classes of prime numbers in class 2 category.

Share and Cite:

V. Yegnanarayanan and A. Parthiban, "Chromatic Number of Graphs with Special Distance Sets-V," Open Journal of Discrete Mathematics, Vol. 3 No. 1, 2013, pp. 1-6. doi: 10.4236/ojdm.2013.31001.

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1] R. Rado, “Axiomatic Treatment of Rank in Infinite Sets,” Canadian Journal of Mathematics, Vol. 1, No. 1949, 1949, pp. 337-343. doi:10.4153/CJM-1949-031-1
[2] N. G. de Bruijn and P. Erdos, “A Color Problem for Infinite Graphs and a Problem in the Theory of Relations,” Proceedings, Series A, Vol. 54, No. 5; Indagationes Mathematicae, Vol. 13, No. 5, 1951, pp. 371-373.
[3] K. J. Falconer, “The Realization of Distances in Measurable Subsets Covering Rn,” Journal of Combinatorial Theory, Series A, Vol. 31, No. 2, 1981, pp. 184-189. doi:10.1016/0097-3165(81)90014-5
[4] H. Hadwiger and H. Debrunner, “Combinatorial Geometry in the Plane,” Holt, Rinehart and Winston, New York, 1964.
[5] V. Yegnanarayanan, “On a Question Concerning Prime Distance Graphs,” Discrete Mathematics, Vol. 245, No. 1-3, February 2002, pp. 293-298. doi:10.1016/S0012-365X(01)00221-7
[6] V. Yegnanarayanan and A. Parthiban, “Chromatic Number of Certain Graphs,” Proceedings of International Conference on Mathematics in Engineering and Business Management, Vol. 1, Chennai, 9-11 March 2012, pp. 115-118.
[7] V. Yegnanarayanan, “Chromatic Number of Graphs with Special Distance Sets, I,” Algebra and Discrete Mathematics, Accepted for Publication in January 2013, to appear.
[8] V. Yegnanarayanan and A. Parthiban, “The Chromatic Number of Graphs with Special Distance Sets-III,” Journal of Mathematical and Computational Science, Vol. 2, No. 5, 2012, pp. 1257-1268.
[9] V. Yegnanarayanan, “The Chromatic Number of Generalized Fibonacci Prime Distance Graph,” Journal of Mathematical and Computational Science, Vol. 2, No. 5, 2012, pp. 1451-1463.
[10] V. Yegnanarayanan and A. Parthiban, “The Chromatic Number of Graphs With Special Distance Sets-II,” Proceedings of International Conference on Mathematical Modelling and Applied Soft Computing, CIT, Vol. 1, Coimbatore, 11-13 July 2012, pp. 305-313.
[11] V. Yegnanarayanan and A. Parthiban, “The Chromatic Number of Graphs With Special Distance Sets-IV,” Proceeding of International Conference on Applied Mathematics and Theoretical Computer Science, Kanyakumari, 2013, to appear.
[12] R. B. Eggleton, P. Erdos and D. K. Skilton, “Coloring the Real Line,” Journal of Combinatorial Theory, Series B, Vol. 39, No. 1, 1985, pp. 86-100; To Erratum, Vol. 41, 1986, p. 139.
[13] R. B. Eggleton, P. Erdos and D. K. Skilton, “Colouring Prime Distance Graphs,” Graphs and Combinatorics, Vol. 6, No. 1, 1990, pp. 17-32. doi:10.1007/BF01787476
[14] A. Kemnitz and H. Kolberg, “Coloring of Integer Distance Graphs,” Discrete Mathematics, Vol. 191, No. 1-3, 1998, pp. 113-123. doi:10.1016/S0012-365X(98)00099-5
[15] M. Voigt and H. Walther, “Chromatic Number of Prime Distance Graphs,” Discrete Applied Mathematics, Vol. 51, No. 1-2, 1994, pp. 197-209. doi:10.1016/0166-218X(94)90109-0
[16] X. Zhu, “The Circular Chromatic Number of Distance Graphs with Distance Sets of Cardinality 3,” Journal of Graph Theory, Vol. 41, No. 3, 2002, pp. 195-207. doi:10.1002/jgt.10062
[17] en.wikipedia.org/wiki/List_of_prime_numbers
[18] L. Halbeisen1 and N. Hungerbuhler, “Number Theoretic Aspects of a Combinatorial Function,” 2000. www.math.uzh.ch/user/halbeis/publications/pdf/seq.pdf
[19] L. Halbeisen and S. Shelah, “Consequences of Arithmetic for Set Theory,” Journal of Symbolic Logic, Vol. 59, No. 1, 1994, pp. 30-40. doi:10.2307/2275247

  
comments powered by Disqus

Copyright © 2020 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.