1. Introduction
The graphs considered in this paper are simple and undirected. A
-coloring of a graph
is an assignment of
different colors to the vertices of
such that adjacent vertices receive different colors. The minimum cardinality
for which
has a
-coloring is called the chromatic number of
and is denoted by
Let
and
be graphs with
, then it is easy to see that
and so
is a monotone function.
We begin with the plane coloring problem. What is the least number of colors needed to color all the points of the Euclidean plane such that no two points of distance one have the same color? The corresponding problem for the real line is easy.
To see this, partition the vertex set of
into two non empty disjoint sets such that their union is
.
That is,
where ![](https://www.scirp.org/html/1-1200108\b5dc216d-da43-4b60-99fa-551baea968ea.jpg)
and
Now color all the vertices
of
with color 1 and the vertices of
with color 2.
As
are independent and
is bipartite the result follows. Clearly
is an infinite graph. The problem of finding the chromatic number of
is enormously difficult. Paul Erdos has mentioned this problem as one of his favorite problems. Although he could not solve this problem he has made a significant progress towards the solution of this problem with a vital result given as follows: First let us state the famous Rado’s Lemma [1].
Lemma 1.1 Let
and
be arbitrary sets. Assume that to any
there corresponds a finite subset
of
. Assume that to any finite subset
, a choice function
is given, which attaches an element of
to each element
of
:
. Then there exists a choice function
defined for all
(
if
) with the following property. If
is any finite subset of
, then there exists a finite subset
, such that, as far as
is concerned, the function
coincides with
.
Theorem 1.1 ([2]) Let
be a positive integer, and let the graph
have the property that any finite subgraph is
-colorable. Then
is
-colorable itself.
Theorem 1.1 allows us to look for the maximum number of colors needed for the finite subsets. It is obvious that
is not a trivial graph. Therefore
. The presence of at least one edgeviz., between (0,0) and (1,1) in
conveys the information that
. Similarly, the presence of a clique of size 3, viz.,
with vertices at
(0,0),
, (1,1) shows that
.
Moreover, it is a fact that four points in the Euclidean two dimensional plane cannot have pairwise odd integer distances. Therefore, a clique of size 4, viz.,
cannot be an induced subgraph of
. But it will be quite interesting to find the coordinates of a unit distance finite subgraph of
such that
The Moser Spindle graph in Figure 1 with a chromatic 4-coloring is a good example to deduce that
.
It is interesting to note that so far no unit distance graph that requires exactly five colors are known. Falconer [3] showed that if the color classes form meaurable sets of
, then at least five colors are needed. Since the construction of non measurable sets requires the axiom of choice, we might have the answer turn out to depend on whether or not we accept the axiom of choice. We can tile the plane with hexagons to obtain a proper 7-coloring of the graph. The result is originally due to Hadwiger and Debrunner [4]. So
.
See Figures 2 and 3 for the lower and upper bounds respectively. Despite the age of this problem, very little progress has been made since the initial bounds on
were discovered shortly after the problem’s creation. This fact is a testament to the difficulty of the problem and in the absence of progress on the main problem, a number of restricted versions and related questions have been studied. We study here the open problem of characterizing the class 4 sets mentioned in the problem for the prime distance graph whose vertex set is
and the distance set
is a subset of not only primes
but are also they are a special set of primes. The authors have already made some progress in [5-11].
2. Prime Distance Graph
A prime distance graph is a graph
with the set of integers as vertex set and with an edge joining two vertices
and
if and only if
where
is the set of all prime numbers.
By a chromatic subgraph of a graph
we mean a minimal subgraph of
with the same chromatic number as
.What class of graphs will include a chromatic subgraph of
for
?
A graph
is color critical if its only chromatic subgraph is
itself. For any positive integer
, let
be the graph comprising
distinct vertices
and
distinct subgraphs
each of which is a copy of
(Where
is the complete graph on n vertices) such that
is adjacent to
and each vertex of
is adjacent to
and
for
.
where
is the cycle on
vertices.
Certain Known Results
Lemma 2.1 ([12]) For any positive integers
the graph
is color critical with
.
Theorem 2.1 ([13])
and hence
.
Proof. Let each integer
be assigned a color class
precisely when
, for
Since integers assigned to the same color differ by a multiple of 4, they are not adjacent in
, so
.
Since
and
is monotone, we have
.
But as
we have
![](https://www.scirp.org/html/1-1200108\18a12773-43d1-46e2-b4cc-6729b11a7604.jpg)
where
is shown in the Figure 4 determined by the vertices
and the subgraphs
with vertex sets
and
respectively. The proof now follows from the Lemma 2.1.
In view of Theorem 2.1, we can allocate the subsets
of
to four classes, according as
has chromatic number 1, 2, 3 or 4. Obviously empty set is the only member of class 1 and every singleton subset is in class 2.
Lemma 2.2
if
consists only of odd integers.
Proof. Partition
into two sets with
![](https://www.scirp.org/html/1-1200108\4f0b4320-cbde-4117-8b70-d6c2443fbb5e.jpg)
such that an integer
if and only if
. Now as the elements of
are even and the elements of
are odd we find that
is an independent set for
. Therefore
is bipartite and hence
. See Figure 5, where = indicates the presence of an edge between any two vertices.
Preposition 1 ([14]) If
is finite and the greatest common divisor of the elements of
is 1 then
(a)
if all
are odd,
![](https://www.scirp.org/html/1-1200108\3c94b021-64da-45a8-a0d6-d9a95c354bc6.jpg)
Figure 5. = indicates the presence of an edge between any two vertices of V1(Z) and V2(Z).
(b)
if no distance element is divisible by 3(c)
if no distance element is divisible by 3 and at least one distance element is even.
Lemma 2.3 If
contains no multiple of a fixed positive integer
, then ![](https://www.scirp.org/html/1-1200108\dcf1d481-5ff4-4833-a331-42facc134cba.jpg)
Proof. Color each vertex
in
by
mod
. Since
and
have the same color if and only if
is a multiple of
, but
contains no multiple of
, this is a proper
-coloring.
For simplicity, we assume that
in the rest of this section. If
, then it is not hard to see that
. For the case of
, where
and
are relatively prime, and so either they are both odd or they are of opposite parity.
Theorem 2.2 If
and
are relatively prime positive odd integers, then ![](https://www.scirp.org/html/1-1200108\d12439e9-fb48-4197-b812-6743f6d8f882.jpg)
Proof. The theorem follows immediately from Lemma 2.3 and the fact that
for any nonempty
.
Theorem 2.3 ([13]) Let
with
. Then
may be classified as follows:
(a)
is in class 2 if
; otherwise
is in class 3 or 4.
(b) If
and
, then
is in class 3.
(c) If
, then
is in class 3.
(d) If
, then
is in class 3.
(e) If
or
, then
is in class 4.
Theorem 2.4 ([13]) For any prime ![](https://www.scirp.org/html/1-1200108\63c2720a-973c-4b15-9d18-fdb48bd22079.jpg)
is in class 3.
Lemma 2.4 ([15]) There exists only a finite number of sets
and
with ![](https://www.scirp.org/html/1-1200108\5a5d6825-919b-4d1d-9acb-ef36a8e93174.jpg)
Theorem 2.5 ([15]) Let
be a set of primes with
and
. Then
holds if and only if
![](https://www.scirp.org/html/1-1200108\b3adbf8b-1063-40e0-85c8-d696cce287c1.jpg)
The proofs of Lemma 2.4 and Theorem 2.5 are available in [15]. Moreover, the authors M. Voigt and H. Walther have shown that there are exactly eight pairs of primes
with ![](https://www.scirp.org/html/1-1200108\878226c5-2691-4bb4-be93-c7d8fd05f659.jpg)
Theorem 2.6 ([16]) Let
with
and
Then
![](https://www.scirp.org/html/1-1200108\cfd15da9-cde3-4562-93dc-c0bf526dafdc.jpg)
3. Some Special Set of Prime Numbers
Consider the following interesting set of prime numbers namely Additive Primes, Deletable Primes, WedderburnEtherington Number Primes, Euclid-Mullin Sequence Primes, Motzkin Primes, Schröder Primes, Catalan Primes, Non-generous Primes, Pell Primes, Primes of Binary Quadratic Form, Primeval Primes, Smarandache-Wellin Primes, Highly Cototient Number Primes, Annihilating Primes, Euclid primes, Fortunate Primes, SchröderHipparchus Number primes, Gaussian Primes, Mersenne Primes, Odd Primes, Primorial Primes, Proth Primes, Regular Primes, Self Primes, Solinas Primes, Super Primes, Delannoy Number Primes, Unique Primes, and Wagstaff Primes. For the definitions of these set of primes refer [17]. However, the existence of an interesting mathematical process that logically leads to the precise definition of an Annihilating prime we mention the same here for the sake of completeness and for the ease of the readers. Each of these set of primes have certain unique properties that make them special and are found to be useful from both theoretical and practical point of view.
Annihilating Primes
Definition 3.1 ([18]) For
let
denote the number of one-to-one sequences— these are sequences without repetitions—we can build with
distinct objects.
(= the empty sequence),
,
,
,
.
Hence,
. Of course, it is easy to find a general expression for
. Since there are ![](https://www.scirp.org/html/1-1200108\c1720f01-721c-41de-aeff-f49466082489.jpg)
possible ways to choose
objects from a set of
(distinct) objects, and since
(distinct) objects give rise to
permutations, we get the following Lemma.
Lemma 3.1
Also the next representation for
is elementary.
Lemma 3.2 For all positive
we have ![](https://www.scirp.org/html/1-1200108\32c82e19-6851-4c06-8c6e-2600e1a576cd.jpg)
Remark: For
the formula does not hold, since
.
Proof. According to Lemma 3.1 we have
![](https://www.scirp.org/html/1-1200108\51316600-12fd-4d39-a097-7fc118fa7c16.jpg)
The following recursive relation for
is an immediate consequence of the second formula in Lemma 3.1.
Lemma 3.3 For all positive
we have
Using this formula, we finally get the following integral representation of
.
Lemma 3.4 For all
we have
![](https://www.scirp.org/html/1-1200108\61fddcd1-e294-4a05-bff5-9d4b96ac725e.jpg)
Notation: Throughout this text we adopt the standard notation
to express that
divides
for
. Moreover, if
then
![](https://www.scirp.org/html/1-1200108\4bddb7e2-0e4a-4837-a012-7b2b599379db.jpg)
denotes the reminder of the division of
by
; and
denotes the greatest common divisor of
and
.
We start our investigation on divisibility properties of
with a simple fact which has first been proved in [19].
Lemma 3.5 For natural numbers
, the following implication holds: If
, then ![](https://www.scirp.org/html/1-1200108\d60985a7-b5f3-4c8c-b4a9-392ffe21e849.jpg)
and
for any
with ![](https://www.scirp.org/html/1-1200108\f7905f94-361d-4d51-9389-b828b5bf5e3d.jpg)
Definition 3.2 If
is a sequence of natural numbers, we define its shadow to be the sequence
given by
where
![](https://www.scirp.org/html/1-1200108\c7cd6395-1f35-4627-b947-9548e677e73a.jpg)
are the shadow sets of the sequence ![](https://www.scirp.org/html/1-1200108\9df133ce-e20b-49e2-b040-1bff1a3fbad3.jpg)
The shadow
counts the sequence entries
which are divisible by
. So, the shadow measures (to a certain extent) how “divisible” the entries of the sequence
are: For example, if only prime numbers occur in the sequence, then its shadow will reflect this fact by being small. If the entries of
have many divisors, the shadow will typically be large.
If
is an arithmetic sequence of first order, then its shadow is periodic, and for the shadow of Euler’s
-function we have
for all ![](https://www.scirp.org/html/1-1200108\86b44650-ee18-4f5d-b341-a102849d4d7d.jpg)
Example: If for a function
there exists an
such that for all
we have
then for all
we have
. Vice versa, if
for all
, then
equals the number of zeros in
. Hence, it is easy to construct different functions which have the same shadow:
0 1 2 3 4 5 6 7···
0 1 2 3 4 5 6 7···
0 1 1 2 3 4 5 6···
0 1 1 1 2 3 4 5···
shadow 0 1 1 1 1 1 1 1···
Definition 3.3 A sequence
is said to have the reduction property, if for all
we have, ![](https://www.scirp.org/html/1-1200108\f325afa2-41b0-4300-aef1-5720c84bcaad.jpg)
Lemma 3.6 The sequence
has the reduction property.
Lemma 3.7 The shadow
of a sequence
which has the reduction property is multiplicative, i.e. if
, then
.
As an immediate consequence we get the following:
Corollary 1 If
is the shadow of
and if
![](https://www.scirp.org/html/1-1200108\ed5e100d-d81c-468c-a6e2-90de0acdfe16.jpg)
is the prime decomposition of
, then
![](https://www.scirp.org/html/1-1200108\1fc783d3-b17f-41b1-b5ad-b04186591db9.jpg)
Therefore, the shadow
of
is fully determined by its values on the powers of prime numbers. But what can we say about
for
prime?
By the reduction property, all elements ![](https://www.scirp.org/html/1-1200108\ca82c2f9-15cd-489b-8a8e-09793a2fddee.jpg)
must be of the form
for some ![](https://www.scirp.org/html/1-1200108\332f3d84-21ff-4ca4-89a1-8c8b7f875fe3.jpg)
and some
. Hence, we get inductively that if
, then
for all positive ![](https://www.scirp.org/html/1-1200108\85c80abd-0f58-40f7-a9a1-df40298508fb.jpg)
Definition 3.4 A prime number
with
is called annihilating.
Preposition 2 If
is divisible by an annihilating prime, then ![](https://www.scirp.org/html/1-1200108\56782e9d-b9b5-4879-8e4c-aaab12397d92.jpg)
Annihilating primes are primes such that
, where
is the shadow of a sequence of natural numbers. First few such primes are: 3, 7, 11, 17, 47, 53, 61, ···
4. Chromatic Number of Certain Prime Distance Graphs
Here we compute the chromatic number of the distance graph:
, when
is a set/subset of any of the above listed primes.
Theorem 4.1
, when
is a finite/ infinite set/subset as the case may be of WedderburnEtherington Number Primes.
Proof. Let
denote the set of Wedderburn-Etherington Number Primes. Note that in
, the set of primes
appears as a proper subset. By Lemma 2.4 and Theorem 2.5, the set of primes
is one of the eight sets of chromatic number 4 class. So
![](https://www.scirp.org/html/1-1200108\dfd608c3-46ef-4c9b-a169-c97b07c01489.jpg)
as
.
Theorem 4.2
, when
is a finite/ infinite set/subset as the case may be of Additive Primes, Deletable Primes, and Euclid-Mullin sequence primes.
Proof. Let
be the set of Additive primes/Deletable primes/ Euclid-Mullin sequence primes. As the set of primes
is a proper subset of
, by Theorem 1.1 and Theorem 2.1
![](https://www.scirp.org/html/1-1200108\d598383a-82f4-4b37-a263-9328b601d197.jpg)
as
.
Theorem 4.3
, when
is a finite/ infinite set/subset as the case may be of 1) Motzkin primes, 2) Catalan primes, 3) Schröder primes, 4) Nongenerous primes, 5) Pell primes, 6) Primeval primes, 7) Primes of binary quadratic form, 8) Smarandache-Wellin primes, and 9) Highly Cototient number primes.
Proof. Let
denote the set of any one of these special class of prime numbers listed in the theorem. All these set of primes have a unique property that an even prime integer 2 is in
but the odd prime integer 3 is not appearing in
. So by Theorem 2.3(b) and Preposition 1(c),
.
Theorem 4.4
, when
is a finite/ infinite set/subset as the case may be of 1) Euclid primes, 2) Fortunate primes, 3) Schröder-Hipparchus Number primes, 4) Gaussian primes, 5) Mersenne primes, 6) Odd primes, 7) Primorial primes, 8) Proth primes, 9) Regular primes, 10) Self primes, 11) Solinas primes, 12) Super primes, 13) Delannoy Number primes, 14) Unique primes, 15) Wagstaff primes, and 16) Annihilating primes.
Proof. Let
denote the set of any one of these special class of prime numbers listed in the theorem. All these special class of primes have a unique property that
does not contain the even prime integer 2 but
has an odd prime integer 3. So by Theorems 2.2 and 2.3(a),
.
Conclusion
A complete characterization of class three sets and class four sets are available in the literature when the cardinality of the distance subset
of
are either 3 or 4. However when the cardinality of
is more than 4 only a little is known. So in this aspect Theorem 4.1, Theorem 4.2 and Theorem 4.3 makes some progress towards the complete characterization of class three and class four sets. Moreover, Theorem 4.4 brings out certain special classes of prime numbers with membership in class 2 category.
5. Acknowledgements
This research is carried out with the financial grant and support of National Board for Higher Mathematics, Government of India under the grant sanction no. 2/ 48(10)/2005/R&D-II/11192/dated 26,Nov,2010.