Chromatic Number of Graphs with Special Distance Sets-V
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 - v∣
D 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.
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 - v∣
D 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.
Cite this paper
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.
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.
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
[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