Chromatic Number of Graphs with Special Distance Sets-V

Venkataraman Yegnanarayanan, Angamuthu Parthiban

Department of Mathematics, Velammal Engineering College, Chennai, India.

DOI: 10.4236/ojdm.2013.31001                

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.

Keywords

Primes; Chromatic Number; Distance Graphs

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