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

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,"

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