Chromatic number of graphs with special distance sets, I
Given a subset D of positive integers, an integer distance graph is a graph G(Z, D) with the set Z of integers as vertex set and with an edge joining two vertices u and v if and only if |u−v| ∈ D. In this paper we consider the problem of determining the chromatic number of certain integer distance g...
Збережено в:
| Дата: | 2014 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | English |
| Опубліковано: |
Інститут прикладної математики і механіки НАН України
2014
|
| Назва видання: | Algebra and Discrete Mathematics |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/152354 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Chromatic number of graphs with special distance sets, I / V. Yegnanarayanan // Algebra and Discrete Mathematics. — 2014. — Vol. 17, № 1. — С. 135–160. — Бібліогр.: 59 назв. — англ. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-152354 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1523542019-06-11T01:25:18Z Chromatic number of graphs with special distance sets, I Yegnanarayanan, V. Given a subset D of positive integers, an integer distance graph is a graph G(Z, D) with the set Z of integers as vertex set and with an edge joining two vertices u and v if and only if |u−v| ∈ D. In this paper we consider the problem of determining the chromatic number of certain integer distance graphs G(Z, D)whose distance set D is either 1) a set of (n + 1) positive integers for which the nth power of the last is the sum of the nth powers of the previous terms, or 2) a set of pythagorean quadruples, or 3) a set of pythagorean n-tuples, or 4) a set of square distances, or 5) a set of abundant numbers or deficient numbers or carmichael numbers, or 6) a set of polytopic numbers, or 7) a set of happy numbers or lucky numbers, or 8) a set of Lucas numbers, or 9) a set of Ulam numbers, or 10) a set of weird numbers. Besides finding the chromatic number of a few specific distance graphs we also give useful upper and lower bounds for general cases. Further, we raise some open problems. 2014 Article Chromatic number of graphs with special distance sets, I / V. Yegnanarayanan // Algebra and Discrete Mathematics. — 2014. — Vol. 17, № 1. — С. 135–160. — Бібліогр.: 59 назв. — англ. 1726-3255 2010 MSC:05C15. http://dspace.nbuv.gov.ua/handle/123456789/152354 en Algebra and Discrete Mathematics Інститут прикладної математики і механіки НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
English |
| description |
Given a subset D of positive integers, an integer distance graph is a graph G(Z, D) with the set Z of integers as vertex set and with an edge joining two vertices u and v if and only if |u−v| ∈ D. In this paper we consider the problem of determining the chromatic number of certain integer distance graphs G(Z, D)whose distance set D is either 1) a set of (n + 1) positive integers for which the nth power of the last is the sum of the nth powers of the previous terms, or 2) a set of pythagorean quadruples, or 3) a set of pythagorean n-tuples, or 4) a set of square distances, or 5) a set of abundant numbers or deficient numbers or carmichael numbers, or 6) a set of polytopic numbers, or 7) a set of happy numbers or lucky numbers, or 8) a set of Lucas numbers, or 9) a set of Ulam numbers, or 10) a set of weird numbers. Besides finding the chromatic number of a few specific distance graphs we also give useful upper and lower bounds for general cases. Further, we raise some open problems. |
| format |
Article |
| author |
Yegnanarayanan, V. |
| spellingShingle |
Yegnanarayanan, V. Chromatic number of graphs with special distance sets, I Algebra and Discrete Mathematics |
| author_facet |
Yegnanarayanan, V. |
| author_sort |
Yegnanarayanan, V. |
| title |
Chromatic number of graphs with special distance sets, I |
| title_short |
Chromatic number of graphs with special distance sets, I |
| title_full |
Chromatic number of graphs with special distance sets, I |
| title_fullStr |
Chromatic number of graphs with special distance sets, I |
| title_full_unstemmed |
Chromatic number of graphs with special distance sets, I |
| title_sort |
chromatic number of graphs with special distance sets, i |
| publisher |
Інститут прикладної математики і механіки НАН України |
| publishDate |
2014 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/152354 |
| citation_txt |
Chromatic number of graphs with special distance sets, I / V. Yegnanarayanan // Algebra and Discrete Mathematics. — 2014. — Vol. 17, № 1. — С. 135–160. — Бібліогр.: 59 назв. — англ. |
| series |
Algebra and Discrete Mathematics |
| work_keys_str_mv |
AT yegnanarayananv chromaticnumberofgraphswithspecialdistancesetsi |
| first_indexed |
2025-07-13T02:53:47Z |
| last_indexed |
2025-07-13T02:53:47Z |
| _version_ |
1837498610596446208 |
| fulltext |
Algebra and Discrete Mathematics RESEARCH ARTICLE
Volume 17 (2014). Number 1. pp. 135 – 160
c© Journal “Algebra and Discrete Mathematics”
Chromatic number of graphs with special
distance sets, I
V. Yegnanarayanan
Communicated by D. Simson
Dedicated to Prof. Dr. R. Balasubramanian, Director, IMSC, India
on his 63rd Birth Day
Abstract. Given a subset D of positive integers, an integer
distance graph is a graph G(Z, D) with the set Z of integers as vertex
set and with an edge joining two vertices u and v if and only if
|u−v| ∈ D. In this paper we consider the problem of determining the
chromatic number of certain integer distance graphs G(Z, D)whose
distance set D is either 1) a set of (n + 1) positive integers for
which the nth power of the last is the sum of the nth powers of the
previous terms, or 2) a set of pythagorean quadruples, or 3) a set of
pythagorean n-tuples, or 4) a set of square distances, or 5) a set of
abundant numbers or deficient numbers or carmichael numbers, or
6) a set of polytopic numbers, or 7) a set of happy numbers or lucky
numbers, or 8) a set of Lucas numbers, or 9) a set of U lam numbers,
or 10) a set of weird numbers. Besides finding the chromatic number
of a few specific distance graphs we also give useful upper and lower
bounds for general cases. Further, we raise some open problems.
1. Introduction
The graphs considered here are mostly finite, simple and undirected.
A k-coloring of a graph G is an assignment of k different colors to
the vertices of G such that adjacent vertices receive different colors. The
2010 MSC: 05C15.
Key words and phrases: chromatic number, prime distance graph, unit distance
graph.
136 Chromatic number of graphs, I
minimum cardinality k for which G has a k-coloring is called the chromatic
number of G and is denoted by χ(G). We denote by N ⊆ Z ⊆ R ⊆ C of the
sets of natural numbers, integers, rational and real numbers respectively.
By G(Rn, D), we mean the distance graph G whose vertex set is Rn and
the edge set is constructed by introducing an edge between two vertices
u and v of G if and only if |u − v| ∈ D. In the same way one can define
G(R1, D) and G(R2, D).
1.1. History of the problem
The chromatic number of the plane problem asks for the minimum
number of colors that are needed to paint all points in the real plane
R2, so that no two points in a given distance are colored alike. The
question seems very natural and basic, but is yet to be fully answered.
The problem goes back to 1950, when Edward Nelson, a graduate student
at the University of Chicago at the time, created the problem working
on the well known four-color problem. He passed the problem to other
mathematicians at the University of Chicago, and soon the question about
the chromatic number of the plane became well known in the mathematical
community (see [48]). The problem sometimes is incorrectly credited
to other mathematicians such as Paul Erdos, Martin Gardner, Hugo
Hadwiger, or Leo Moser. Actually, the question was probably published
for the first time in Martin’s Gardner Mathematical Games" column in
Scientific American" in 1960 [13]. Although in the last nearly 60 years the
chromatic number of the plane resisted all efforts aiming at an ultimate
answer, a considerable amount of research discussing partial answers
to this problem, or investigating related problems, accumulated in the
mathematical literature. The following bounds on the chromatic number
are well known: 4 ≤ chromatic number of the plane ≤ 7. We shall briefly
see how these bounds are obtained. At this point, however, let us mention
that it has been shown by Saharon Shelah and Alexander Soifer [49,50]
that the answer to the problem may depend on the choice of axioms of
the set theory.
The corresponding problem for the real line R is easy. That is,
χ(G(R, D = {1})) = 2. To see this, partition the vertex set V (R) of G into
two non empty disjoint sets such that their union is R. That is, V (R) =
V1 ∪V2, where V1 =
∞⋃
n=−∞
[2n, 2n+1) and V2 =
∞⋃
n=−∞
[2n+1, 2n+2). Now
color all the vertices of V1 with color 1 and the vertices of V2 with color 2.
As Vi, i = 1, 2 are independent and G(R, D = {1}) is bipartite the result
V. Yegnanarayanan 137
follows. Clearly G(R2, {1}) is an infinite graph. The problem of finding
the chromatic number of G(R2, {1}) 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 it with a vital result given in Theorem 1.1. First we state
the famous Rado’s Lemma [33].
Lemma 1.1. Let M and M1 be arbitrary sets. Assume that to any v ∈ M1
there corresponds a finite subset Av of M . Assume that to any finite subset
N ⊂ M1, a choice function xN (v) is given, which attaches an element
of Av to each element v of N :xN (v) ∈ Av. Then there exists a choice
function x(v) defined for all v ∈ M1 (x(v) ∈ Av if v ∈ M1) with the
following property. If K is a finite subset of M1, then there exists a finite
subset N(K ⊂ N ⊂ M1), such that, as far as K is concerned, the function
x(v) coincides with xN (v) : x(v) = xN (v)(v ∈ K).
Theorem 1.1. Let k be a positive integer, and let G be a graph with the
property that any finite subgraph is k-colorable. Then G is k-colorable
itself [3].
Proof. Let M be the set of all k-colors, and let M1 be the set of all
vertices of G. We always choose Av = M. To any finite N(N ⊂ M1) there
corresponds a finite subgraph of G, consisting of the vertices belonging to
N , and all edges between these vertices as far as these belongs to G. This
subgraph is assumed to be k-colorable, and so we have a function xN (v),
defined for v ∈ N, taking its values in M by Lemma 1.1. Now the function
x(v) defines a coloration of the whole graph G. To show that opposite
ends of any edge get different colors, we consider an arbitrary edge e, and
we denote the set of its two end-points v1, v2 by K. Let N be a finite set
satisfying K ⊂ N ⊂ M1, x(v) = xN (v ∈ K). To N there corresponds a
finite graph GN which is k-colorable by the function xN (v); GN contains e.
Therefore xN (v1) 6= xN (v2), and so x(v1) 6= x(v2).
Theorem 1.1 allows us to look for the maximum number of colors
needed for the finite subsets of the vertex set of G. It is obvious that
G(R2, {1}) is not a trivial graph. Therefore χ(G(R2, {1})) 6= 1. The
presence of at least one edge, viz., between (0,0) and (1,1) in G(R2, {1})
conveys the information that χ(G(R2, {1})) ≥ 2. Similarly, the presence
of a clique of size 3, viz., K3 with vertices at (0,0),(1
2 ,
√
3
2 ), (1,1) shows that
χ(G(R2, {1})) ≥ 3. Moreover, it is a fact that four points in the Euclidean
two dimensional plane R2 cannot have pairwise odd integer distances.
138 Chromatic number of graphs, I
Therefore, a clique of size 4, viz., K4 cannot be an induced subgraph
of G(R2, {1}). But it will be quite interesting to find the coordinates
of a unit distance finite subgraph of G(R2, {1}) such that χ(G1) = 4.
The Moser Spindle graph in Figure 1 with a chromatic 4-coloring is a
good example to deduce that χ(G(R2, {1})) ≥ 4. It is interesting to note
that so far no unit distance graph that requires exactly five colors are
known. Falconer [9] showed that if the color classes form measurable sets
of R2, 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 [16].
So 4 ≤ χ(G(R2, {1})) ≤ 7. Despite the age of this problem, very little
progress has been made since the initial bounds on χ(G(R2, {1})) 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.
Erdos et al in [5] have proved that χ(G(Z, {2, 3, 5})) = 4 and hence
χ(G(Z, P )) = 4. So we can allocate the subsets D of P to four classes,
according as G(Z, D) 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. We
study here the open problem of characterizing the Class 3 and Class 4 sets.
In particular we concentrate on those distance sets D where D is a subset
of not only primes P but also they are a special set of primes. A motivation
considering the special types of primes stems from the fact that these
special class of primes have not only interesting properties but also have
stunning applications in various fields. For instance., the wonderful work
of Von Mag.Ingrid G.Abfalter in [55] has shown an interesting application
involving graph vertex coloring and Fibonacci numbers in the problem of
sequence design of nucleic acids. Moreover Voigt in [54]has characterized
the 4 sets when the the distance set D ⊂ P is of cardinality 4. The integer
distance graph G(Z, D) with distance set D = {d1 < d2 < . . . } has the
set of integers Z as the vertex set and two vertices x, y ∈ Z are adjacent if
and only if |x − y| ∈ D. Integer distance graphs were first systematically
studied by Eggleton, Erdös and Skilton [5] and have been studied by
others since then see [41,53,58,59].
In the present paper we consider the problem of determining the
chromatic number of certain integer distance graphs whose distance set
D is either 1) a set of (n + 1) positive integers for which the nth power
V. Yegnanarayanan 139
Figure 1. The Moser Spindle
of the last is the sum of the nth powers of the previous terms; Here,
the smallest sets for known values of n are: for n = 3, the distance set
D1 = {3, 4, 5; 6}, for n = 4, the distance set D2 = {30, 120, 272, 315; 353},
for n = 5, the distance set D3 = {19, 43, 46, 47, 67; 72}, for n = 7, the
distance set D4 = {127, 258, 266, 413, 430, 439, 525; 568}, for n = 8, the
distance set D5 = {90, 223, 478, 524, 748, 1088, 1190, 1324; 1409}. Like
this one can continue to construct distance sets for other values of n.
But the process of such a construction will be arduous, or 2) a set of
pythagorean quadruples or 3) a set of pythagorean n-tuples or 4) a set of
square distances or 5) a set of abundant numbers or deficient numbers
or carmichael numbers, or 6) a set of polytopic numbers, or 7) a set of
happy numbers or lucky numbers, or 8) a set of Lucas numbers or 9) a
set of U lam numbers, or 10) a set of weird numbers. Besides finding the
exact chromatic number of a few specific distance graphs we also give
useful upper and lower bounds for general cases.
2. Chromatic number of a distance graph
with typical distance sets
We say a coloring c of the set Z of integers is a pattern periodic
coloring if there is an integer p, and a permutation f of the set of colors
such that for every x ∈ Z, we have c(x) = f(c(x − p). We call p the period
of the pattern periodic coloring c, and call f the color permutation of c.
Theorem 2.1. If D1 = {3, 4, 5; 6}, then χ(G(Z, D1)) = 3.
First we prove the following two results.
Lemma 2.1. χ(G(Z, D)) = 2 if D consists only of odd integers.
140 Chromatic number of graphs, I
Proof. Partition V (Z) into two sets with V (Z) = V1(Z) ∪ V2(Z) such that
an integer x ∈ Vi(Z) if and only if x ≡ i(mod 2). Now as the elements
of V1(Z) are even and the elements of V2(Z) are odd we find that Vj
is an independent set for j = 1, 2. Therefore G is bipartite and hence
χ(G(Z, D)) = 2.
Lemma 2.2. Let D be a subset of Z. If for a given positive integer n,
Dn is the set of all those elements of D built by integers divisible by n,
then χ(G(Z, D)) ≤ minn∈N n(|D0|n + 1) where D0 ⊂ D is that subset of
D built by integers divisible by n.
Proof. Partition the vertices of G(Z, D) into residue classes Vi = {v ∈
V (G) = Z : v ≡ i(mod n)}, i = 0, 1, . . . , n − 1, with respect to arbitrary
positive integer n. If ui and vi ∈ Vi then ui is adjacent to wi if and only
if |ui − wi| ∈ Dn. Since |D0| + 1 is upper bound of χ(G(Z, D)) if D0 is
finite and since the induced subgraphs < V0 >, < V1 >, . . . , < Vn−1 > are
pairwise isomorphic and therefore isomorphic to G(Z, (1/n)Dn) which has
distance set {(d/n) : d ∈ Dn
0 }, we obtain χ(G(Z, (1/n)Dn)) ≤ |D0|n + 1.
This implies that the vertices of each Vi, i = 0, 1, . . . , n−1, can be colored
with |D0|n + 1 colors. The number of residue classes is n and therefore all
the vertices of G(Z, D) are are to be colored by n(|D0|n + 1) colors.
Proof of Theorem 2.1. Now as D1 consists of both odd and even integers
we infer from Lemma 2.1 that G(Z, D1) contains odd cycles and hence
χ(G(Z, D)) ≥ 3. Further it follows from Lemma 2.2 that χ(G(Z, D)) ≤ 5.
Now partition the vertex set of Z as V (Z) = V1(Z) ∪ V2(Z) ∪ V3(Z)
where V1(Z) = {x ∈ Z : x ≡ 0, 1, 2(mod 9)}; V2(Z) = {x ∈ Z : x ≡
3, 4, 5(mod 9)} and V3(Z) = {x ∈ Z : x ≡ 6, 7, 8(mod 9)}. It is easy to
see that each Vj(Z) is an independent set for j = 1, 2, 3. Now assign one
color each to these three sets. This results in a chromatic 3-coloring of
G(Z, D) and hence χ(G(Z, D)) = 3.
What makes D1 = {3, 4, 5; 6} special?
Note that 63 = 33 + 43 + 53. This gives rise to the following question.
Consider a set of (n + 1) positive integers for which the nth power of the
last is the sum of the nth powers of the previous terms. The smallest
sets for known values of n are : for n = 3 we have D1 = {3, 4, 5; 6},
for n = 4 we have D2 = {30, 120, 272, 315; 353}, for n = 5 we have
D3 = {19, 43, 46, 47, 67; 72}, for n = 7 we have D4 = {127, 258, 266, 413,
430, 439, 525; 568}, for n = 8 we have D5 = {90, 223, 478, 524, 748, 1088,
V. Yegnanarayanan 141
1190, 1324; 1409}. We observe that each Di for 2 ≤ i ≤ 5 consists of
both odd and even integers. Moreover gcd(Di) = 1. Hence it follows from
Theorem 2.1 that χ(G(Z, D)) ≥ 3. We conjecture that χ(G(Z, Di)) ≤ n+2,
for i ≥ 2. We inch forward towards this conjecture with the following
result.
Theorem 2.2. Suppose that D is a finite set of integers with d = max{y :
y ∈ D}. If the subgraph of G induced by the set {0, 1, . . . , kd/(k! + d − 1)}
is k-colorable, then the graph G(Z, D) is also k-colorable.
Proof. Consider the set S of all sequences s of k colors of length d. Define
an equivalence relation on S as follows. We say two sequences of colors
s = (x1, x2, . . . , xd) and s′ = (y1, y2, . . . , yd) are equivalent, denoted by,
s ∼ s′, if there is a permutation f of the k colors such that yi = f(xi)
for i = 1, 2, . . . , d. Each equivalence class contains k! sequences and
hence there are kd/k! equivalence classes. Let t = kd/k!. Consider a
k-coloring of the graph G(Z, D), which is a two way infinite sequence
of colors. Each segment of this sequence of length d is an element of
S. Let si = (c(i), c(i + 1), . . . , c(i + d − 1)). Consider the sequences
s0, s1, . . . , st. By the Pigeonhole principle, there are integers i < j, such
that si ∼ sj . Hence there is a permutation f of the colors such that
sj = f(si). That is., c(j + k) = f(c(i + k)) for k = 0, 1, . . . , d − 1. Now
define a partial pattern periodic coloring c′ of the distance graph G(Z, D)
with period j − i as follows: For i ≤ x ≤ j + d − 1, let c′(x) = c(x); for
x ≥ j + d, let c′(x) = f(c′(x − (j − i))). It can be easily seen by recursion
that c′ is defined on the set of all integers x ≥ i. For any x ≥ j, let
c′(x) = f(c′(x − (j − i))). We claim that c′ is a proper coloring of the
subgraph of G(Z, D) induced by the integers x ≥ i. Suppose not then
let y be the smallest integer such that there exists an integer x < y such
that c′(x) = c′(y) and y − x ∈ D. Since c is a proper coloring of G(Z, D)
and c′ agrees with c on the segment {i, i + 1, . . . , j + d − 1}, it follows
that y ≥ j + d. As d = max{y : y ∈ D}, it follows that x ≥ j and hence
x − (j − i) ≥ i. Therefore c′(y − (j − i)), c′(x − (j − i)) are defined, and
c′(y) = f(c′(y − (j − i))) and c′(x) = f(c′(x − (j − i))). However, by
the choice of y, we know that c′(y − (j − i)) 6= c′(x − (j − i)) because
(y − (j − i)) − (x − (j − i)) = y − x ∈ D. This is a contradiction, as f is a
permutation of the colors. We extend c′ to the whole set Z of integers as
follows: For x ≤ i − 1, let c′(x) = f1(c′(x + (j − i))). The same argument
shows that c′ is a proper coloring of G. So j − i ≤ kd/k!. So if c is a
proper k-coloring of the segment {0, 1, . . . , kd/(k! + d − 1)}, then there
exists an integer 0 ≤ i < j ≤ kd/k! such that the restriction of c to the
142 Chromatic number of graphs, I
segment {i, i + 1, . . . , j + d − 1} can be extended to a pattern periodic
coloring of the whole graph.
In view of Theorem 2.2, for the distance set D2 =
{30, 120, 272, 315; 353} if we could find a 3-coloring for the sub-
graph induced by the set {0, 1, . . . , 3353 /(3! + 352)} then the whole
graph G(Z, D2) is 3-colorable. Similarly for the other distance sets Dj
we can apply the Theorem 2.2. Although finding a 3-coloring for a
huge set like {0, 1, . . . , 3353/358} seems to be difficult there exists an
algorithm [4] to determine χ(G(Z, Dj)). That is, let q = max(Dj). Then
χ(G(Z, Dj)) ≤ q + 1. Consider the colorings of the subgraph G(Z, D)
induced by S = [1, qq + q]. Then for k ≤ q, if < S > has a proper
k-coloring, then χ(G(Z, D)) ≤ k. Let k ≤ q, and suppose that < S > has
proper k-coloring. The number of k-coloring of a block of q consecutive
integers is qq at most. Since < S > contains qq + q such blocks, two such
blocks contained in S (say [a, a + q − 1] and [b, b + q − 1], with a < b)
receive the same pattern of colors. We extend the coloring of [a, b + q − 1]
to a coloring f of Z by the rule f(i + a − b) = f(i) for all i. This is a
proper coloring of G(Z, D) and so χ(G(Z, Dj)) ≤ k. However we ask here
two important questions.
1) What is the exact chromatic number of G(Z, Dj) for a given j?
2) How do we determine the elements of Dj for any given j?
We also raise the following conjecture.
Conjecture 1. Let k ≥ 3. Determining whether χ(G(Z, D)) ≤ k for
finite sets D is NP -complete.
3. Chromatic number of pythagorean tuples
Xuding Zhu [59] has proved that if a < b < c are integers with
gcd(a, b, c) = 1 and that D = {a, b, c} and G = G(R, D) then χ(G(R, D)) =
2 if all the integers a, b, c are odd; χ(G(R, D)) = 4 if a = 1, b = 2
and c ≡ 0(mod 3); χ(G(R, D)) = 4 if a + b = c and a 6≡ b(mod 3);
χ(G(R, D)) = 3 for all other cases.
In view of the above all pythagorean triples (a, b, c) with D = {a, b, c}
has chromatic number 3 for its distance graph G(Z, D). This is because, a
typical pythagorean triple has at least one even integer so the chromatic
number cannot be 2. Further as 12+22 6= 3k2 for any k and a2+b2 6= (a+b)2
it cannot have chromatic number 4.
V. Yegnanarayanan 143
3.1. Pythagorean quadruples
In a rectangular solid, the length of an interior diagonal is determined
by the formula a2 + b2 + c2 = d2, where a, b, c are the dimensions of the
solid and d is the diagonal. When a, b, c, d are integers then a pythagorean
quadruples is formed. Mordell [30] developed a solution to this Diophantine
equation using integer parameters (m, n, p), where m + n + p ≡ 1(mod 2)
and gcd(m, n, p) = 1. The formulae are a = 2mp, b = 2np, c = p2 −
(n2 + m2), d = p2 + (n2 + m2). However, the pythagorean quadruples
(36, 8, 3, 37) cannot be generated by Mordells formulae, since c must be
smaller of the odd numbers and 3 = p2 − (n2 + m2), 37 = p2 + (n2 + m2),
implies 40 = 2p2 and it means 20 = p2 and so p is not an integer.
We note that, for positive integers a and b, where a or b or both are
even, there exists integers c and d such that a2 + b2 + c2 = d2. When
a and b are both odd no such integers c and d exist. When a and b are
of opposite parity, then c = (a2 + b2 − 1)/2 and d = (a2 + b2 + 1)/2.
This is because, d2 − c2 = (d + c)(d − c) = [(a2 + b2 + 1)/2 + (a2 +
b2 − 1)/2][(a2 + b2 + 1)/2 − (a2 + b2 − 1)/2] = [a2 + b2](1) = a2 + b2,
therefore a2 + b2 + c2 = d2. As a and b differ in parity, c and d given
above are integers. Also we see that c and d are consecutive integers.
Therefore gcd(a, b, c, d) = 1 even when gcd(a, b) 6= 1. If and b are both
even then c = ((a2 + b2)/4) − 1 and d = ((a2 + b2)/4) + 1. This is because,
16(d2 − c2) = (a2 + b2 + 4)2 − (a2 + b2 − 4)2 = 16(a2 + b2). Therefore
a2 + b2 + c2 = d2. Since a and b are both even, c and d given above are
integers. Notice that if a − b ≡ 0(mod 4) then (a2 + b2)/4 is even and so c
and d are consecutive odd integers and hence in this case gcd(a, b, c, d) = 1.
But if a − b ≡ 2(mod 4) then (a2 + b2)/4 is odd and we get that c and d
are consecutive even integers, and gcd(a, b, c, d) 6= 1. Finally, if a and b are
both odd, then a2 ≡ b2 ≡ 1(mod 4). Since c2 ≡ 0(mod 4) or c2 ≡ 1(mod 4),
and similarly for d2, we have a2 + b2 + c2 ≡ 2(mod 4) 6= d2 for any integer
d or a2 +b2 +c2 ≡ 3(mod 4) 6= d2 for any integer d. Hence no pythagorean
quadruple exist in this case.
In the view of the above discussion, first let us consider only those
pythagorean quadruples (a, b, c, d) where a and b are either of opposite
parity or both even with a, b, c and d are all distinct. Let D = {a, b, c, d} be
such a distance set. We notice by Theorem 2.1 that 3 ≤ χ(G(Z, D)) ≤ 5.
As matter of investigative instance consider the case where the distance set
is D = {2, 3, 6, 7}. Clearly (2, 3, 6, 7) is a pythagorean quadruple. (22 +32 +
62 = 72). By Lemma 2.2 we can easily see that χ(G(Z, {2, 3, 6, 7})) ≤ 4 as
there is no element divisible by 4. Now we claim that χ(G(Z, {2, 3, 6, 7})) ≥
144 Chromatic number of graphs, I
4. Let C be any arbitrary chromatic 3-coloring of G(Z, {2, 3, 6, 7}) with
colors c1, c2 and c3. And let C(ci) denote the set of all elements of Z with
color ci. First we note that C cannot color any three consecutive integers
with the same color. This is because, if i, i + 1, i + 2 share the same color,
then i + 2 − i = 2 and the fact that 2 ∈ {2, 3, 6, 7} forces an edge between
i + 2 and i in G(Z, {2, 3, 6, 7}). Now, without loss of generality, assume
that C assigns the color c1 to i, i + 1. Then the elements i − 1, i + 2 must
be colored with either of the remaining colors c2 or c3 under C. Again by
a similar argument, we notice that both i − 1, i + 2 cannot be colored by
either c2 or c3 under C. So assume that i+2 is assigned the color c2 and i−1
the color c3 under C. We iteratively build up the elements with colors c1
or c2 or c3 by carefully repeating the above argument wherever necessary.
This process leads to the stage where: C(c1) = {i, i+1, i−4, i+5, i−5, ...},
C(c2) = {i + 2, i + 3, i − 3, ...} and C(c3) = {i − 1, i − 2, i + 4, ...}. Now the
element i+6 cannot be colored by any of these 3 colors c1 or c2 or c3. This
is because, (i + 6) − i = 6, (i + 6) − (i + 3) = 3 and (i + 6) − (i + 4) = 2 and
the fact that 2, 3, 6∈ {2, 3, 6, 7} forces (i + 6, i), (i + 3, i + 6), (i + 4, i + 6)
to belong to the edge set of G(Z, {2, 3, 6, 7}). This contradiction shows
that C requires at least 4 colors to chromatically color G(Z, {2, 3, 6, 7}).
Hence χ(G(Z, {2, 3, 6, 7})) ≥ 4. Thus we have the following theorem.
Theorem 3.1. χ(G(Z, {2, 3, 6, 7}) = 4.
Note. It is interesting to notice that the distance set D = {2, 3, 6, 7}
serves as an evidence for the existence of an extremal graph for the
graph equation χ(G(Z, D)) = 4. On similar lines one can prove that
χ(G(Z, 1, 4, 8, 9) = 4. These two instances motivate us to conjecture that
χ(G(Z, D)) = 4, whenever D is a distance set of distinct pythagorean
quadruple {a, b, c, d} where a and b are either of opposite parity or both
even.
3.2. Pythagorean n-tuples
One can find formulae for pythagorean n-tuples on similar lines as
in pythagorean quadruples. Suppose that S = (a1, a2, . . . , an−2), where
ai is an integer, and let T be the cardinality of the odd integers in
S. If T 6≡ 2(mod 4) then there exist integers an−1 and an such that
a2
1 + a2
2 + · · · + a2
n−1 = a2
n. To see this, let T ≡ 1(mod 2). This means
T ≡ 1(mod 4) or T ≡ 3(mod 4). Now set an−1 = (a2
1+a2
2+· · ·+a2
n−2−1)/2
and an = (a2
1 + a2
2 + · · · + a2
n−2 + 1)/2. Then we have a2
n − a2
n−1 =
(an + an−1)(an − an−1) =
∑n−2
j=1 a2
j . Again let T ≡ 0(mod 4). Here set
V. Yegnanarayanan 145
an−1 = ((a2
1 +a2
2+· · ·+a2
n−2)/4)−1 and an = ((a2
1 +a2
2 +· · ·+a2
n−2)/4)+1.
Then we have a2
n − a2
n−1 = (an + an−1)(an − an−1) =
∑n−2
j=1 a2
j . Finally if
T ≡ 2(mod 4), then a2
1+a2
2+· · ·+a2
n−2 ≡ 2(mod 4). Since a2
n−1 ≡ 0(mod 4)
or a2
n−1 ≡ 1(mod 4), we have a2
1 +a2
2 + · · ·+a2
n−2 +a2
n−1 ≡ 2(mod 4) 6= a2
n
for any integer an or a2
1 + a2
2 + · · · + a2
n−2 + a2
n−1 ≡ 3(mod 4) 6= a2
n for
any integer an. Hence no pythagorean n-tuple exists in this case.
Now consider only those pythagorean n-tuples
(a1, a2, . . . , an−2, an−1, an) where
1) the cardinality of odd integers in the set {a1, a2, . . . , an−2} is not
congruent to 2 modulo 4, and
2) aj ’s are all distinct for 1 ≤ j ≤ n.
Let D = {a1, a2, . . . , an−2, an−1, an} be a distance set satisfying the
above condition. Then as gcd(D) = 1, we can easily deduce that 3 ≤
χ(G(Z, D)) ≤ n + 1. The existence of extremal graphs for the graph
equation χ(G(Z, D)) = 5 when D is a pythagorean quadruple set as in
Theorem 3.1 indicates the probable existence of an extremal graph for
the graph equation χ(G(Z, D)) = n + 1 when D is a set of pythagorean
n-tuple of the above type. It would be interesting to find one such D.
4. Chromatic number of square distance graphs
What is the chromatic number of a square distance graph G(Z, D)
where D = {d2
1, d2
2, . . . , d2
n} is a finite set of all positive squares. First
observe that any pythagorean triple induces a complete graph on three
vertices, K3 in the square distance graph. This is because, consider the
Euclid’s fundamental formula for generating a pythagorean triple. Suppose
that m and n are positive integers with m > n. Then a = m2 − n2,
b = 2mn, c = m2 + n2 forms a pythagorean triple. Now consider an
integer distance graph G(Z, D) with distance set D = {a2, b2, c2} where
a, b, c forms a pythagorean triple. Consider a subgraph G1 of G on the
vertex set {02, a2, c2}. Clearly a2 − 02 = a2, c2 − 02 = c2 and c2 − a2 =
(m2 + n2)2 − (m2 − n2)2 = 4m2n2 = (2mn)2 = b2 are all elements of D.
Therefore G1
∼= K3. So we deduce that χ(G(Z, D)) ≥ 3, where D is a set
of pythagorean triples.
Next we observe that no pythagorean quadruple induces a complete
graph on four vertices, K4 in the square distance graph. This is because;
consider the fundamental formula for generating a pythagorean quadruple.
Suppose that l, m, n are positive integers. Then a = (l2 − m2 − n2),
146 Chromatic number of graphs, I
b = (2lm), c = (2ln) and d = (l2 + m2 + n2) forms a pythagorean
quadruple. Consider an integer distance graph G(Z, D) with distance set
D = {a2, b2, c2, d2} where a, b, c and d forms a pythagorean quadruple.
Note that a2 − b2, a2 − c2, d2 − a2, d2 − b2, d2 − c2, b2 − c2 are different
from a2, b2, c2 and d2. Hence no three of them goes along with 0 to form
a vertex set of K4.
However we also know that if a set D of positive integers contains
a multiple of every positive integer and the distance graph G(Z, D) has
a finite uniquely k-colorable subgraph then χ(G(Z, D)) ≥ k + 1. In
view of this, as K3 is uniquely 3-colorable and D contains a multiple
of every positive integer we have χ(G(Z, D)) ≥ 4. Further Eggleton [5]
has showed the existence of a K4 in the square distance graph with
vertices 02, 6722, 6802, 6972 producing differences that are squares namely
6802 − 6722 = 1042, 6972 − 6802 = 1532 and 6972 − 6722 = 1852. Again
as K4 is uniquely 4-colorable we deduce that χ(G(Z, D)) ≥ 5. Our
hand/computer calculations indicate that the upper bound may not be
finite.
Problem. Decide? whether or not 5 is a best lower bound for the square
distance graph.
In view of this discussion we generalize our observation to state that
no pythagorean n-tuple will induce a complete graph on n vertices for
n ≥ 4.
5. Chromatic number of abundant number,
deficient number and carmichael number distance graphs
An abundant number is a number n for which the sum of divisors
σ(n) > 2n or the sum of proper divisors s(n) > n. The value σ(n) − 2n or
s(n) − n is known as the abundance. The first few abundant numbers are
12, 18, 20, 24, 30, 36, 40, 42, 48, 54, 56, 60, 66, 70, 72, . . .
The smallest abundant odd number is 945. The smallest abundant number
not divisible by 2 or 3 is 5391411025. Infinitely many even and odd
abundant numbers exist. Every multiple of abundant number is abundant.
Although the proof of Theorem 5.1 follows from the Lemma 2.2 we
give an alternative proof as follows.
Theorem 5.1. Suppose that G(Z, D) is an integer distance graph with
D = {12, 24, 36, . . . , 12k} a subset of the set of all abundant numbers.
Then χ(G(Z, D)) ≤ 4.
V. Yegnanarayanan 147
Proof. Suppose D = {12, 24, 36, . . . , 12k} is a distance set for the graph
G(Z, D). Then we observe that the set {0, 12, 24, 36, . . . , 12k} = D of
integers induces a clique of size k + 1. Therefore χ(G(Z, D)) ≥ k + 1. To
exhibit a k+1 chromatic coloring, partition V (Z) as V (Z) =
⋃k
i=0[(k+1)Z+
i], where [(k+1)Z+i] is the equivalence class of (k+1)Z+i. That is, V (Z) =
{0, k + 1, 2k + 2, . . . } ∪ {1, k + 2, 2k + 3, . . . } ∪ · · · ∪ {k, 2k + 1, 3k + 2, . . . }.
Set Vi = [(k + 1)Z+ i] for i = 0, 1, . . . , k. Assign a color c(v) = i whenever
v ∈ Vi. This yields a proper (k + 1)-chromatic coloring for G(Z, D).
Note. Suppose that G(Z, D) is an integer distance graph with D =
{18, 30, 42, . . . , 12k +6} a subset of the set of all abundant numbers. Then
by, Lemma 2.2, χ(G(Z, D)) ≤ 4.
An deficient number is a number n for which the sum of divisors
σ(n) < 2n or the sum of proper divisors s(n) < n. The value 2n − σ(n)
or n − s(n) is known as the deficiency. The first few deficient numbers are
1, 2, 3, 4, 5, 7, 8, 9, 10, 11, 13, 14, 15, 16, 17, 19, 21, 22, 23, 25, 26, 27, . . .
All odd numbers with one or two distinct prime factors are deficient.
All proper divisors of a deficient number are deficient.
Note. Consider the integer distance graph G(Z, D), where D is a finite set
of deficient numbers. Since gcd(D) = 1 and D contains odd numbers we get
from Lemma 2.2 of Theorem 2.1 that 3 ≤ χ(G(Z, D)) ≤ minn∈N n(|D0|n +
1) where D0 ⊂ D is the subset of D built by integers divisible by n.
A Carmicheal number is a composite integer n which satisfies the con-
gruence bn−1 ≡ 1(mod n) for all integers b which are relatively prime to
n. These numbers are important because they pass the Fermat primality
test but are not actually primes. As numbers become larger, Carmicheal
numbers become rare. For example, there are 20,138,200 Carmicheal
numbers between 1 and 1021 (approximately one in 50 billion numbers).
A positive composite integer n is a Carmicheal number if and only if n is
square free and for all prime divisors p of n, it is true that p − 1|n − 1. It
follows from this that all Carmicheal numbers are odd. That is, any even
composite number that is square free (and hence only one prime factor of
two) will have at least one odd prime factor, and thus p − 1|n − 1 results
in an even dividing an odd, a contradiction. The first such number is 561.
The next few such numbers are 1105, 1729, 2465, 2821, 6601, 8911, etc.
So if D is a set of all Carmicheal numbers then it follows from Lemma
2.1 of Theorem 2.1 that χ(G(Z, D)) = 2.
148 Chromatic number of graphs, I
6. Chromatic number of polytopic number distance graphs
Suppose that D is the set of triangular numbers, D =
{1, 3, 6, 10, . . . , n+1c2}. Form a distance graph G(Z, D). As gcd(D) = 1
and D contains odd numbers we get from Lemma 2.2 of Theorem 2.1
that 3 ≤ χ(G(Z, D)) ≤ minn∈N n(|D0|n + 1) where D0 ⊂ D is the subset
of D built by integers divisible by n. If D is a set of tetrahedral numbers,
D = {1, 4, 10, . . . , n+2c3} then 3 ≤ χ(G(Z, D)) ≤ minn∈N n(|D0|n + 1)
where D0 ⊂ D is the subset of D built by integers divisible by n.
The term figurate number is used for members of different sets of
numbers generalizing from triangular members to different shapes (polyg-
onal numbers) and different dimensions (polyhedral numbers). The rth
diagonal of pascal’s triangle for r ≥ 0 consists of the figurate numbers for
the r-dimensional analogs of triangles. The simplicial polytopic numbers
for r = 1, 2, 3, 4, . . . are n+0c1, n+1c2 , n+2c3, n+3c4, . . . , n+r−1cr called
respectively linear numbers, triangular numbers, tetrahedral numbers, pen-
tachoron numbers, . . . , r-topic numbers. In view of this, if D is a set of any
of the above polytopic numbers then 3 ≤ χ(G(Z, D)) minn∈N n(|D0|n + 1)
where D0 ⊂ D is the subset of D built by integers divisible by n.
7. Chromatic number of happy number and lucky number
distance graphs
A happy number is defined by the following process. Starting with any
positive integer, replace the number by the sum of the squares of its digits,
and repeat the process until the number equals 1 (where it will stay), or
it loops endlessly in a cycle which does not include 1. Those numbers for
which this process ends in 1 are happy numbers, while those that do not
end in 1 are unhappy numbers. For example, 19 is happy, as 12 + 92 = 82,
82 + 22 = 68, 62 + 82 = 100, 12 + 02 + 02 = 1. If D is a finite set of happy
numbers, D = {1, 7, 10, 13, 19, 23, . . . } then gcd(D) = 1 and by Lemma
2.2 of Theorem 2.1, we have 3 ≤ χ(G(Z, D)) minn∈N n(|D0|n + 1) where
D0 ⊂ D is the subset of D built by integers divisible by n. A happy prime
is a number that is both happy and prime. The happy prime numbers
are 7, 13, 19, 23, 31, . . . . If D is a set of happy prime numbers then it
follows from Lemma 2.1 that χ(G(Z, D)) = 2. So it follows easily that
if D is a set of pythagorean n-tuples with all integers happy prime then
χ(G(Z, D)) = 2 for n ≥ 2.
V. Yegnanarayanan 149
A lucky number is a natural number in a set which is generated by a
“sieve”. Begin with a list of integers starting with 1.
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25.
Every second number is eliminated (all even numbers), leaving only
the odd integers.
1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25.
The second term in this sequence is 3. Every third number which
remains in the list is eliminated.
1, 3, 7, 9, 13, 15, 19, 21, 25.
The third surviving number is now 7, so every seventh number that
remains is eliminated.
1, 3, 7, 9, 13, 15, 21, 25.
As this procedure is repeated indefinitely, the survivors are the lucky
numbers.
1, 3, 7, 9, 13, 15, 21, 25, 31, 33, 37, 43, 49, 51, 63, . . .
A lucky prime is a lucky number that is prime. If the distance set
D is a set of lucky numbers or a set of lucky prime numbers then the
corresponding distance graph G(Z, D) has chromatic number 2. This
follows from the fact that the lucky numbers and lucky prime numbers
are odd and from Lemma 2.1 of Theorem 2.1.
8. Chromatic number of lucas number distance graphs
A Lucas number is defined as: Ln = 2, if n = 0; 1 if n = 1; Ln−1 +Ln−2
if n > 1. The sequence of Lucas numbers begins: 2, 1, 3, 4, 7, 11, 18, 29, 47,
76, 123, . . . . If D is a finite set of Lucas numbers then gcd(D) = 1 and by
Lemma 2.2 of Theorem 2.1 we have 3 ≤ χ(G(Z, D)) ≤ minn∈N n(|D0|n+1)
where D0 ⊂ D is the subset of D built by integers divisible by n. A Lucas
prime is a Lucas number that is prime. A first few Lucas primes are 2, 3,
7, 11, 29, 47, 199, 521, 2207, 3571, 9349, . . . .
If A is a set of Lucas prime numbers then as A ⊂ P , the set of all
primes, it follows that χ(G(Z, A)) ≤ χ(G(Z, P )) = 4. We claim that
150 Chromatic number of graphs, I
χ(G(Z, A)) ≥ 3. Choose from A, 2 and any Lucas prime p. Then we
note that G(Z, A) contains a cycle v0v1v2, . . . , vpwv0 where vi = 2i for
0 ≤ i ≤ p, and w = p. As this cycle has order p + 2, which is odd, it has
chromatic number 3. Hence the claim follows.
Suppose that χ(G(Z, A)) = 3. Let C be any arbitrary chromatic 3-
coloring of G(Z, A) with colors c1, c2 and c3. And let C(ci) denote the
set of all elements of Z with color ci. First we note that C cannot color
any three consecutive integers with the same color. This is because, if
i, i + 1, i + 2 share the same color, then i + 2 − i = 2 and the fact that
2 ∈ A forces an edge between i + 2 and i in G(Z, A). Now, without loss of
generality, assume that C assigns the color c1 to i, i+1. Then the elements
i − 1, i + 2 must be colored with either of the remaining colors c2 or c3
under C.
Again by a similar argument, we notice that both i − 1, i + 2 cannot
be colored by either c2 or c3 under C. So assume that i + 2 is assigned
the color c2 and i − 1 the color c3 under C. We iteratively build up
the elements with colors c1 or c2 or c3 by carefully repeating the above
argument wherever necessary. This process leads to the stage where:
C(c1) = {i, i + 1, i − 4, i + 5, ...}, C(c2) = {i + 2, i + 3, i − 3, ...} and
C(c3) = {i − 1, i − 2, i + 4, ...}. Now the element i + 6 cannot be colored
by any of these 3 colors c1 or c2 or c3. This is because, (i + 6) − (i − 5) =
11, (i + 6) − (i + 3) = 3 and (i + 6) − (i + 4) = 2 and the fact that 2, 3,
11∈ A forces (i + 6, i − 5), (i + 3, i + 6), (i + 4, i + 6) to belong to the edge
set of G(Z, A). This contradiction shows that C requires at least 4 colors
to chromatically color G(Z, A). Hence χ(G(Z, A)) ≥ 4. That is.,
Theorem 8.1. χ(G(Z, A)) = 4, if A is a set of all Lucas primes.
In view of 8.1, we can allocate the subsets A1 of A to four classes
according as G(Z, A) has chromatic number 1, 2, 3 or 4. Obviously the
empty set is the only member of class 1. The following results are some
of the interesting easy consequences whose proofs are given for the sake
of completeness.
Theorem 8.2. Every singleton subset of the set of all Lucas primes is in
class 2.
Proof. Note that for every positive integer r ∈ A we have V (G(Z, {r})) =
(
⋃r−1
i=0 (2rZ + i)) ∪ (
⋃2r−1
i=r (2rZ + i)) = V1 ∪ V2 say. Then as each Vj is
independent for j = 1, 2, . . . , we find that G(Z, {r}) is bipartite and so
χ(G(Z, {r})) = 2.
V. Yegnanarayanan 151
Theorem 8.3. Let A1 ⊆ A with |A1| ≥ 2. Then A1 may be classified as
follows:
a) A1 is in class 2 if 2 6∈ A1; otherwise A1 is in class 3 or 4.
b) If 2 ∈ A1 and 3 6∈ A1 then A1 is in class 3.
c) If {2, 3} ⊆ A1 ⊆ {p ∈ A : p ≡ ±2(mod 5)} then A1 is in class 3.
d) If {2, 3} ⊆ A1 ⊆ {p ∈ A : p ≡ ±2, ±3, 7(mod 14)} then A1 is in
class 3.
Proof. The statement a) follows immediately by one argument in the
course of proof of Theorem 5.1. To see b), a proper 3-coloring of G(Z, A1)
is obtained by assigning the integer x to color class i precisely when
x ≡ i(mod 3) for 0 ≤ i ≤ 2. To see c) assign an integer x to color class i
precisely when x ≡ 2i or 2i + 1(mod 5) for 0 ≤ i ≤ 1 and assign x to color
class 2 if x ≡ 4(mod 5). We see that the difference between any two integers
in the same class is congruent to 0 or ±1(mod 5). So no such pair is adjacent
in G(Z, A1). Now with a) if 2 ∈ A1, it follows that A1 is in class 3. To prove
d) assign each integer x to color class i, where i = 0 when x ≡ 0, 1, 5, 6
or 10(mod 14); i = 1, when x ≡ 2, 3, 7, 11 or 12(mod 14); i = 2, when
x ≡ 4, 8, 9 or 13(mod 14). The difference between any two integers in the
same color class is congruent to 0, ±1, ±4, ±5, and ±6(mod 14). So no
such pair is adjacent in G(Z, A1) if A1 ⊆ {p ∈ A : p ≡ ±2, ±3, 7(mod 14)}.
With a) if 2 ∈ A1, then A1 is in class 3.
Theorem 8.4. For any Lucas prime p, the set A1 = {2, 3, p} is in class 3.
Proof. In view of Theorem 8.3, it is enough to demonstrate a proper
3-coloring for G(Z, {2, 3, p}). First suppose that p = 6k + 1 for some
k > 0. Assign each integer x to color class i, where 0 ≤ i ≤ 2 as follows:
x ≡ a(mod 6k + 4) with −4 ≤ a ≤ 6k. If a ≥ 0 then x → i when a = 2i
or 2i + 1(mod 6). Also x → 0 if a = −4; x → 1 if a = −3 or −2; x → 2
if a = −1. (Here by x → i, we mean that the integer x is assigned to
the color class i). No integers in the same color class differ by ±2 or
±3(mod 6k + 4). So this is a proper coloring. If p = 6k − 1 for some k ≥ 2,
then for any integer x, let x ≡ (mod 6k + 2) with −14 ≤ a ≤ 6k − 12.
If a ≥ 0 then x → i when a = 2i or 2i + 1(mod 6) with 0 ≤ i ≤ 2.
As in the proof of Theorem 8.3 (d), when a < 0 we assign x → 0 if
a ∈ {−14, −13, −9, −8, −4}, x → 1 if a ∈ {−12, −11, −7, −3, −2}, x → 2
if a ∈ {−10, −6, −5, −1}. No two integers in the same color class differ
by ±2 or ±3(mod 6k + 2). So this is a proper coloring and covers all the
cases.
152 Chromatic number of graphs, I
Note. Normally we denote the complete graph on n vertices by Kn.
Theorem 8.5. If A1 ⊂ A is a subset of set A of Lucas primes then the
complete graph K3 is not an induced subgraph of G(Z, A1).
Proof. Suppose G(Z, A1) contains K3, then such a K3 cannot have two
edges of even length. This is because; the longest edge would then be at
least 4, a contradiction. Therefore at least two edges of K3 must have odd
length. This means the third edge must have even length which being a
Lucas prime, must be 2. But then the lengths of the two odd edges must
therefore be twin primes. We observe from the list of Lucas primes the
gap between any two Lucas primes is getting bigger and bigger and hence
there exist no twin Lucas primes.
Theorem 8.5 implies obviously that K4 also is not an induced subgraph.
In this situation, it would be interesting to find a finite subset A1 of Lucas
primes so that the corresponding distance graph has chromatic number 4.
9. Chromatic number of U lam number distance graphs
U lam sequence starts with U1 = 1 and U2 = 2. Then for n > 2, Un is
defined to be the smallest integer that is the sum of two distinct earlier
terms in exactly one way. By the definition, 3 = 1 + 2 is an U lam number;
and 4 = 1 + 3 is an U lam number. (The sum 4 = 2 + 2 is not, because the
previous terms must be distinct.) The integer 5 is not an U lam number,
because 5 = 1 + 4 = 2 + 3. The first few terms are 1, 2, 3, 4, 6, 8, 11,
13, 16, 18, 26, 28, 36, 38, 47, 48, 53, 57, 62, 69, 72, 77, 82, 87, 97, 99. If
D is a finite set of U lam numbers then gcd(D) = 1 and by Lemma 2.2
of Theorem 2.1 we have 3 ≤ χ(G(Z, D)) ≤ minn∈N n(|D0|n + 1) where
D0 ⊂ D is the subset of D built by integers divisible by n. The first U lam
numbers that are also prime numbers are 2, 3, 11, 13, 47, 53, 97, 131,
197, 241, 409, 431, 607, 673, 739, 751, 983, 991, 1103, 1433, 1489. If A
is a set of U lam prime numbers then as A ⊂ P , the set of all primes, it
follows that χ(G(Z, A)) ≤ χ(G(Z, P )) = 4. As A1 = {2, 3, 11, 13} ⊂ A
and χ(G(Z, A1)) = 4 by [54] we have 4 = χ(G(Z, A1)) ≤ χ(G(Z, A)) and
hence χ(G(Z, A)) = 4. Note that G(Z, A1) cannot contain a K4. Suppose
not then there is a subgraph K3 with vertices 0, 11, 13. If the fourth
vertex of K4 is v and v < 13 then the subgraph K3 with vertices 0, 13, v
must have one edge of length 2, and v 6= 11 implies v = ±2. If v = −2
then the adjacency of v and 13 require that 15 is a prime. If v = 2 then
the adjacency of v and 11 require that 9 is also a prime. So in either case,
V. Yegnanarayanan 153
we get a contradiction. In view of this we can allocate the subsets A1 of
A to four classes according as G(Z, A) has chromatic number 1, 2, 3 or
4. Obviously the empty set is the only member of class 1. The results
obtained for Lucas primes in Theorem 8.2, Theorem 8.3 and Theorem
8.4 are true for U lam primes also. Unlike Theorem 8.5 for Lucas primes
we see that U lam prime distance graph has K3 as an induced subgraph.
This is because the vertex set induced by the integers {0, 11, 13} forms a
K3 in G(Z, A).
10. Chromatic number of weird number distance graphs
A natural number whose sum of the proper divisors (divisors includ-
ing 1 but not itself) is greater than the number but no subset of those
divisors sums to the number itself is called a weird number. The smallest
weird number is 70. Its proper divisors are 1, 2, 5, 7, 10, 14, and 35; these
sum to 74, but no subset of these sums to 70. The first few weird numbers
are 70, 836, 4030, 5830, 7192, 7912, 9272, 10430, . . . . It has been shown
that an infinite number of weird numbers exist. It is not known if any odd
weird numbers exist; if any do, they must be greater than 232 ≈ 4 × 109.
So if D is a set of weird numbers then by Lemma 2.2 of Theorem 2.1 we
have 3 ≤ χ(G(Z, D)) ≤ minn∈N n(|D0|n + 1) where D0 ⊂ D is the subset
of D built by integers divisible by n.
11. Coloring unit distance graphs of higher dimensions
The unit distance graph in n dimensions over the field F ⊆ {R,Q},
is also denoted by Un
F is the graph G defined by V (G) = F n, and two
vertices are adjacent if and only if they are at Euclidean distance 1. Most
of the interest in unit distance graphs stems from coloring. The famous
open problem is to determine the chromatic number U2
R. This problem is
also called plane coloring problem.
There has been more success in determining the chromatic number of
Un
Q for small values of n. The chromatic numbers of U2
Q, U3
Q and U4
Q are
known and good bounds are known for U5
Q, U6
Q, U7
Q and U8
Q.
Another important result about the rational graphs is about connec-
tivity. The rational unit distance graphs are not necessarily connected.
Chilakamarri [20–22] showed that Un
Q is connected when n ≥ 5 and is
not connected when n ≤ 4. Generally to understand the structure of the
entire graph it suffices to understand the structure of the components.
154 Chromatic number of graphs, I
Since Qn is isomorphic under a rational translation, the components must
all be translates of each other.
The 2-colorability of U3
Q and U2
Q was originally shown by Johnson [17]
using the ideas from Group Theory. We however observe here that they
are bipartite and hence the result follows obviously. To see this, it is
enough to establish the bipartity of U3
Q as U2
Q is an induced subgraph of
U3
Q and χ is a monotonic function. Suppose we have a cycle in U3
Q with
edge set {ai
d
, bi
d
, ci
d
}n
i=1. Then we have that a2
i + b2
i + c2
i = d2. Examining
this modulo 4, we see that if d is even, then ai, bi, ci are even for all i.
If we consider this in lowest terms, we may assume that d is odd. If we
examine the equation modulo 8, we see that exactly one of ai, bi, ci must
be odd. Since the edges form a cycle we must have
n∑
i=1
(ai, bi, ci) = (0, 0, 0).
This implies that
n∑
i=1
(ai + bi + ci) = 0. Examining this modulo 2, we have
that
n∑
i=1
1 = 0 or n = 0. Thus n is even and the cycle must have even
length. As the cycle chosen here is arbitrary, all cycles must have even
length and hence the graph must be bipartite.
More generally, the question of computation of chromatic number of
Un
F can be asked for any metric space in any dimension. For instance, the
Un
R under any norm, the n-dimensional grid Un
Z under l1-norm and even
the integer line under Archimedean or non-Archimedean norms. The first
breakthrough paper for lower and upper bounds under the Euclidean norm
are by Frankel and Wilson [10], and Larman and Rogers [26]. The lower
bound was improved by Raigorodskii [37]-[40]. The problem has been gen-
eralized to other metric spaces by Benda and Perels [2], Raigorodskii [40],
Woodall [56], and to any normed space by Furedi and Kang [11].
While a coloring of a metric space in high dimensions has the flavours
of combinatorial geometry, an analogous question asked for the integer line
has more of a flavor of combinatorial number theory. One other interesting
variation is the consideration of a distance graph on the set of integers Z
under the p-adic norms. Let p be a prime number. Then any non zero
rational number x can be uniquely written in the form x = r
s
pl where
l ∈ Z and r, s are integers not divisible by p. One defines the p-adic norm
of x by ‖x‖p = 1
pl . This gives rise to a non-Archimedean norm on the
rational numbers Q. A p-adic distance graph G(Z, D) with the vertex
set of Z and distance set D ⊂ Q such that two integers x, y are adjacent
if and only if ‖x − y‖p ∈ D for some prime p. Here the distance sets D
V. Yegnanarayanan 155
should be reasonably chosen subsets of Q. Ruzza et.al [41] have proved
the following result.
Theorem 11.1. Let D = {d1, d2, ...} be an infinite distance set. Then
χ(G(Z, D)) is finite whenever inf di+1
di
> 1. Moreover this result is tight
in the sense that every growth speed smaller than this admits a distance
set D with infinite chromatic number.
Via p-adic norms, Jeong-Hyun Kang and Hiren Maharaj [18] gave
bounds on the chromatic number of distance sets that are quite dense
and have divisibility constraints. So the chromatic numbers are applicable
even in the case that inf di+1
di
= 1. In fact they have given a sufficient
condition for the distance graph G(Z, D) to have finite chromatic number:
”Let D = {d1, d2, ...} be a distance set. For each prime number p, let
D(p) be the set of all powers pn of p such that pn divides di but pn+1 does
not divide di for some i. Then χ(G(Z, D)) ≤ min{p|D(p)| : p is a prime}.”
Conjecture 2. Suppose D is a given distance set. The chromatic number
of Euclidean distance graph G(Z, D) is infinite if and only if for every
finite partition of D =
⋃
1≤j≤k
Dj there exists j, 1 ≤ j ≤ k, such that some
multiple of every integer appear in the set Dj = {d1 < d2 < ...} and
inf
di∈Dj
di+1
di
= 1.
In the above conjecture, considering finite partitions is important. For,
if D = {n!, n! + 1 : n ∈ Z}, then D contains multiples of every integer
and inf
di∈D
di+1
di
= 1. Partition D = D1 ∪ D2 where D1 = {n! : n ∈ Z}
and D2 = {n! + 1 : n ∈ Z}. Then inf di+1
di
> 1 for j = 1, 2 and Theorem
11.1 of Ruza et.al [41] implies that the chromatic number of both graphs
G(Z, Dj) are finite. Their finite union graph G(Z, D) also has finite
chromatic number.
12. Practical motivation for the study of vertex distance
graphs
In chemical graph theory there is a large number of molecular topolog-
ical indices based on vertex distances. The best known among them are
the classical Wiener [52] and Balaban [1] indices, but quite a few others
are also encountered. Of them it worth to mention the family of molecu-
lar topological indices introduced in [43–47], the Harary index [32], the
family of hyper-Wiener indices [34–36] and the recently proposed Szeged
156 Chromatic number of graphs, I
index [19] For review and comparative studies of vertex-distance-based
molecular structure descriptors see the articles published by Mihalic and
others [27–29].
A seemingly unrelated field of activity in contemporary chemical graph
theory is the search for methods to canonically label the atoms of chemical
compounds so that the labeling is as much as possible structure-based
(and not conventional) and as much as possible convenient for computer-
aided manipulation with structural information. Of the numerous works
in this direction we mention S . B. Elk’s pioneering efforts aimed at
polycyclic molecules, especially at benzenoid systems [6–8].
There are results that are related to both the canonical labeling of the
vertices of benzenoid systems and to vertex distances. In order to be able
to formulate them familiarity with the basic features of the (mathematical)
theory of Hamming graphs is essential [23].
The molecular graphs of benzenoid hydrocarbons will be referred to
as benzenoid systems; their properties are discussed in [15].In mathe-
matical literature the very same objects are called "hexagonal systems"
or "hexagonal animals [15]. Notice that the definition of a benzenoid
system as given in the next para (the same as given in [15]) excludes
coronacondensed systems, benzene modules, helicenes, and other related
polycyclic molecules. Hence, the benzenoid systems considered are either
cata- or pericondensed.
Sandi Klaviar et.al in [23] defined a benzenoid system G as a finite
connected plane graph with no cut vertices in which every interior region
is bounded by a regular hexagon of side length 1. A straight line segment
C in the plane with end points P1 and P2 is called a cut segment if C
is orthogonal to one of the three edge directions, each P1 and P2 is the
center of an edge, and the graph obtained from G by deleting all edges
intersected by C has exactly two connected components. An elementary
cut C0 of a cut segment C is the set of all edges intersected by C. By Cuv
we will denote the elementary cut containing an edge uv. We refer to [42]
for more information on the defined terms.
Besides the possibility of applying the Hamming labeling of a hexago-
nal system for nomenclature purposes it can be used for fast calculation
of molecular parameters based on the graph distance. As an example the
Wiener index W (G) is equal to the sum of distances dG(u, v) taken over
all pairs of vertices u, v of G. The advantage of W (G) is that one can store
information about the graph G just by representing l(u), u ∈ V (G), and
then being able to compute various distance-based parameters without
really reconstructing the graph.
V. Yegnanarayanan 157
Acknowledgement
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. The
author also thanks A. Parthiban his Ph.D. student for useful discussions.
References
[1] Balaban, A. T., Highly discriminating distance-based topological index, Chem.
Phys. Lett. 89(1982), 399-404.
[2] Benda, M, Perles, A., Colorings of metric spaces, Geombinatorics 9 (2000), 113-126.
[3] de Bruijn, N.G and Erdos, P., A color problem for infinite graphs and a problem
in the theory of relations, Proceedings, Sereies A, 54, No.5 and Indag. Math., 13,
No.5, (1951).
[4] Eggleton, R.B, Erdös, P, Skilton, D.K., Colouring prime distance graphs, Graphs
and Combinatorics 6 (1990), 17–32.
[5] Eggleton, R.B, Erdös, P, Skilton, D.K., Coloring the real line, J. Combin. Theory
Ser. B 73 (1985), 86–100.
[6] Elk, S. B., Canonical orderings of hexagons that; (1) nearly meet the intent of
Patterson’s nomenclature rules and (2) orient a molecule for 33(1990), 709-716.
purposes of assigning a IUPAC name. Polycyclic Arm". Comp. I(1990), 109-121.
[7] Elk, S. B. A., Canonical ordering of polybenzenes and polymantanes using prime
number factorization technique, J. Math. Chem. 4(1990), 55-68.
[8] Elk, S. B., Graph theoretical algorithm to canonically name the isomers of the
regular polyhedranes, J. Chem. Inf. Comput. Sci. 32(1992), 14-22.
[9] Falconer, K.J., The realization of distances in measurable subsets covering Rn, J.
of Combinatorial Theory Ser.A, 31(2):(1981), 184-189.
[10] Frankl, P, Wilson, R.M., Intersection theorems with geometric consequences, Com-
binatorica 1(1981), 357-368.
[11] Fiuredi, Z, Kang, J-H., Distance graph on Zn with l1-norm, Theoret. Comput.
Sci., Special issue on Combinatorics of the Discrete Plane and Tilings 319 (2004),
357–366.
[12] Z. Fiuredi, Kang, J-H., Covering n-space by convex bodies and its chromatic
number, Disc. Math., Special issue in honor of M. Simonovits 308 (2008), 4495–
4500.
[13] Gardner, M., The celebrated four-color map problem of topology, Sci. Amer. 203
(1960), 218-226.
[14] Gutman, I., Selected properties of the Schultz molecular topological index, J. Chem.
Inf. Comput. Sci. 34(1994), 1087-1089.
[15] Gutman, I, Cyvin, S. J., Introduction to the Theory of Benzenoid Hydrocarbons;
Springer-Verlag, Berlin, 1989.
[16] Hadwiger, H and Debrunner, H., Combinatorial Geometry in the plane, Holt,
Rinehart and Winston, New York, 1964.
158 Chromatic number of graphs, I
[17] Johnson, P.D., Coloring abelian groups, Discrete Math., 40(2-3):(1982), 219-223.
[18] Kang, J-H and Maharaj, H., Distance Graphs from p-adic Norms, Integers, 10(2010),
379-392.
[19] Khadikar, P. V, Deshpande, N. V, Kale, P. P, Dobrynin, A, Gutman, I, Domotor,
G., The Szeged index and some of its analogies with the Wiener index, J. Chem.
Inf. Comput. Sci. 35(1995), 547-550.
[20] Kiran B. Chilakamarri., Unit-distance graphs in rational n-spaces, Discrete Math.,
69(3):(1988), 213-218.
[21] Kiran B. Chilakamarri., On the chromatic number of rational five-space, Aequa-
tiones Math., 39(2-3):(1990), 146-148.
[22] Kiran B. Chilakamarri., The unit-distance graph problem: a brief survey and some
new results, Bull. Inst. Combin. Appl., 8:(1993), 39-60.
[23] Klaviar, S, Gutman, I and Mohar, B., Labeling of Benzenoid Systems which Reflects
the Vertex-Distance Relations, J. Chem. Inf. Comput. Sci. 35(1995), 590-593.
[24] Klein, D. J, Mihalic. Z, PlavSic. D, Trinajstic, N., Molecular topological index. A
relation with the Wiener index, J. Chem. Inf. Comput. Sci. 32(1992), 304-305.
[25] Knop, J. V, Muller, W. R, Szymanski. K, Trinajstic. N., On the determinant of the
adjacency-plus-distance matrix as a topological index for characterizing alkanes,
J. Chem. Inf. Compur. Sci. 31(1991), 83-84.
[26] Larman, D.G, Rogers, C.A., The realization of distances within sets in Euclidean
space, Mathematika 19 (1972), 1-24.
[27] Mihalic, Z, Nikolic, S, Trinajstic, N., Comparative studies of the descriptors derived
from the distance matrix, J. Chem. Inf Comput.Sei. 32(1992), 28-37.
[28] Mihalic, Z, Trinajstic, N., A graph-theoretical approach to structureproperty rela-
tionships, J. Chem. Educ. 69(1992), 701 -712.
[29] Mihalic, Z, Veljan, D, Amic, D, Nikolic, S, PlavSic, D, Trinajstic, N., The distance
matrix in chemistry, J. Math. Chem. 11(1992), 223-258.
[30] Mordell, L.J., Diophantine Equations, London Academic Press 1969.
[31] Muller, W. R, Szymanski. K, Knop. J. V, Trinajstic, N., Molecular topological
index, J. Chem. Inf. Comput. Sci. 30(1990), 160-163.
[32] Plavsic, D, Nikolic, S, Trinajstic, N, Mihalic, Z., On the Harary index for the
characterization of chemical graphs, J. Math. Chem. 12(1993), 235-250.
[33] Rado, R., Axiomatic treatment of rank in infinite sets, Canad.J.Math.1, (1949),
337-343.
[34] Randic, M., Novel molecular descriptor for structure-property studies, Chern. Phys.
Lett. 211(1993), 478-483.
[35] Randic, M, Guo, X, Oxley, T, Krishnapriyan, H., Wiener matrix: Source of novel
graph invariants, J. Chem. Inf. Comput. Sci. 1993.
[36] Randic, M, Guo, X, Oxley, T, Krishnapriyan, H, Naylor, L., Wiener matrix invari-
ants, J. Chem. Inf. Compul. Sci. 34(1994), 361-367.
[37] Raigorodskii, A.M., On the chromatic number of a space, Russ. Math. Surveys 55
(2000), 351–352.
V. Yegnanarayanan 159
[38] Raigorodskii, A.M., Borsukâs problem and the chromatic numbers of some metric
spaces, Russ. Math. Surveys 56 (2001), 103–139.
[39] Raigorodskii, A.M., The Erd́’osâHadwiger problem, and the chromatic number of
finite geometric graphs, Doklady Russian Acad. Sci. 392 (2003), 313–317.
[40] Raigorodskii, A.M., On the chromatic number of a space with q-norm, Russ. Math.
Surveys 59 (2004), 973–975.
[41] Ruzsa, I.Z, Tuza, Zs, Voigt, M., Distance graphs with finite chromatic number, J.
Combin. Theory Ser. B 85(1) (2002), 181–187.
[42] Sachs, H., Perfect matchings in hexagonal systems, Combinatorica 4(1984), 89-99.
[43] Schultz, H. P., Topological organic chemistry. 1. Graph theory and topological
indices of alkanes, J. Chem. Inf. Cumput. Sci. 29(1989), 227-228.
[44] Schultz. H. P, Schultz, E. B, Schultz, T. P., Topological organic chemistry. 2. Graph
theory, matrix determinants and eigenvalues.and topological indices of alkanes, J.
Chem. Inf. Comput. Sci. 30(1990), 27-29.
[45] Schultz, H. P, Schultz, T. P., Topological organic chemistry. 3. Graph theory, binary
and decimal adjacency matrices, and topological indices of alkanes, J. Chem. Inf.
Comput. Sci. 31(1991), 144-147.
[46] Schultz, H. P, Schultz, E. B, Schultz, T. P., Topological organic chemistry. 4. Graph
theory. matrix permanents and topological indices of alkanes, J. Chem. In Compur.
Sei. 32(1992), 69-72.
[47] Schultz, H. P, Schultz, T. P., Topological organic chemistry. 5. Graph theory,
matrix Hafnians and Pfaffians, and topological indices of alkanes, J. Chem. In &
Comput. Sei. 32(1992), 364-366.
[48] Soifer, A., Chromatic number of the plane & its relatives I. The problem & its
history, Geombinatorics 12 (2003), no. 3, 131-148.
[49] Soifer, A and Shelah, S., Axiom of choice and chromatic number of the plane, J.
Combin.Theory Ser. A 103 (2003), no. 2, 387-391.
[50] Soifer, A and Shelah, S., Axiom of choice and chromatic number: examples on the
plane, J. Combin. Theory Ser. A 105 (2004), no. 2, 359-364.
[51] Trinajstic, N., Chemical Graph Theon, 2nd revised ed.: CRC Press: Boca Raton,
FL, 1992.
[52] Wiener, H., Structural determination of paraffin boiling points, J. Am.Chem. Soc.
69(1947), 17-20.
[53] Voigt, M., On the chromatic number of distance graphs, J. Inform. l Process.
Cybernet. EIK 28 (1992), 21–28
[54] Voigt, M., Die chromatische Zahl einer Speziellen Klasse unendlicher Graphen,
Dissertations Schrift, Techn. Univ. Hemanau, 1992.
[55] Von Mag.Ingrid G.Abfalter., Nucleic Acid Sequence Design as a Graph Coloring
Problem, Dissertation zur Erlangung des akademischen Grades Doktor rerum
naturalium, Vorgelegt der Fakultat fur chemie der Universitat Wien, am Institut
fur Theoretische Chemie und Molekulare Struktur Biologie, Nov, 2005.
[56] Woodall, D.R., Distances realized by sets covering the plane, J. Combinatorial
Theory Ser. A 14 (1973), 187-200.
160 Chromatic number of graphs, I
[57] Woodall, D.R., Distances realized by sets covering the plane, J. Combinatorial
Theory Ser. A 14 (1973), 187–200.
[58] Zhu, X., Pattern periodic coloring of distance graphs, J. Combin. Theory B 73
(1998), 195–206.
[59] Zhu, X., Diophantine approximations and coloring of distance graphs, Manuscript
1998.
Contact information
V. Yegnanarayanan Department of Science&Humanities, Vignan
University, Guntur-522213, India
E-Mail: prof.yegna@gmail.com
Received by the editors: 19.04.2012
and in final form 05.03.2013.
|