=Paper=
{{Paper
|id=Vol-3072/paper2
|storemode=property
|title=Proving a Conjecture on 8-Distance Coloring of the Infinite Hexagonal Grid
|pdfUrl=https://ceur-ws.org/Vol-3072/paper2.pdf
|volume=Vol-3072
|authors=Sasthi C. Ghosh,Subhasis Koley
|dblpUrl=https://dblp.org/rec/conf/ictcs/GhoshK21
}}
==Proving a Conjecture on 8-Distance Coloring of the Infinite Hexagonal Grid==
https://ceur-ws.org/Vol-3072/paper2.pdf
Proving a Conjecture on 8-Distance Coloring of the
Infinite Hexagonal Grid?
Sasthi C. Ghosh and Subhasis Koley
Advanced Computing and Microelectronics unit
Indian Statistical Institute, 203 B. T. Road, Kolkata 700108, India
Emails: sasthi@isical.ac.in, subhasis.koley2@gmail.com
Abstract. Given p ∈ N, a p distance coloring is a coloring f : V → {1, 2, · · · , n}
of the vertices of G such that f (u) 6= f (v) for all pair of vertices u and v in G
where d(u, v), the distance between u and v, is at most p. Here d(u, v) is de-
fined as the minimum number of edges required to connect u and v in G. The
p distance chromatic number λp (G) of a graph G is the minimum n such that
G admits a p distance coloring of G. Such type of distance coloring is relevant
when frequency assignment problem is formulated as a graph coloring problem.
In the context of frequency assignment problem, sometimes cellular network can
be modelled as an infinite hexagonal grid TH . Therefore λp (TH ) has practical
relevance. For even p ≥ 8, it was conjectured by Jacko" and Jendrol [Discussiones
2 #
p 3 4
Mathematicae Graph Theory, 2005] that λ (TH ) = p+ where [x]
8 3
1 1
is an integer, x ∈ R and x − < [x] ≤ x + . In this paper, we prove that
2 2
λ8 (TH ) = 33 which coincides with the conjectured value.
Keywords: Distance coloring · hexagonal grid · lower bound · conjecture
1 Introduction
Assigning frequencies to the communication channels in a communication network is
one of the fundamental challenges as frequencies must be allotted in such a way that
interference cannot occur during communication. The frequency channel assignment
problem (CAP) can be modelled as a graph coloring problem where vertices are repre-
sented as users and proximity between vertices can be measured in terms of minimum
number of edges between them and color of a vertex represents frequency assigned to
the corresponding user [1]. Sometimes CAP is formulated as a variant of graph col-
oring problem where two vertices at distance at most p cannot have same color. This
type of graph coloring is called a p distance coloring of a graph G(V, E). Wegner [2]
introduced p distance coloring of G as a coloring f : V → {1, 2, · · · , n} of the vertices
of G such that f (u) 6= f (v) for all pair of vertices u and v in G where d(u, v) ≤ p.
Here d(u, v), the distance between u and v in G, is defined as the minimum number of
?
Copyright c 2021 for this paper by its authors. Use permitted under Creative Commons Li-
cense Attribution 4.0 International (CC BY 4.0).
2 Sasthi C. Ghosh et al.
edges required to connect u and v in G. The objective of such coloring problem is to
find the p distance chromatic number λp (G) where λp (G) is the minimum n such that
G admits a p distance coloring of G. Several authors studied the distance graph color-
ing problems [7–9]. Sometimes CAP in cellular network can be modelled as a graph
coloring problem in infinite regular hexagonal grid or honeycomb grid TH . In Fig. 1,
honeycomb representation of TH have been shown. The coordinates of the vertices of
TH have also been shown here.
(0, 4) (1, 4) (2, 4) (3, 4) (4, 4)
(0, 3) (1, 3) (2, 3) (3, 3) (4, 3)
(0, 2) (1, 2) (2, 2) (3, 2) (4, 2)
(0, 1) (1, 1) (2, 1) (3, 1) (4, 1)
(0, 0) (1, 0) (2, 0) (3, 0) (4, 0)
Fig. 1: Honeycomb representation of TH and coordinates of its vertices.
Several authors studied p distance graph coloring for TH [3–6]. When p is odd, the
exact value of λp (TH ) has been determined in [5]. But for even p, the exact value of
λp (TH ) has not been determined yet [5, 7, 10, 11]. In [5], it was conjectured that for
every even p ≥ 8,
" 2 #
p 3 4
λ (TH ) = p+ (1)
8 3
1 1
([x] is an integer, x ∈ R and x − < [x] ≤ x + ) and is still an open problem.
2 2
It has been shown in [5] that
0 3 2 3
|TH (V 0 , E 0 )| = p + p+1 (2)
2 2
0
where TH (V 0 , E 0 ) is the maximum subgraph of TH such that d(u, v) ≤ 2p for every
pair of vertices u, v ∈ V 0 . Using equation (2), a lower bound of λ2p (TH ) was obtained
Proving a Conjecture on 8-Distance Coloring of the Infinite Hexagonal Grid 3
in [5]. The result is as follows:
2p 3 2 3
λ (TH ) ≥ p + p + 1 + 1. (3)
2 2
equation (3) implies that λ8 (TH ) ≥ 32 [5]. But this value is one less than that of the
value obtained from equation (1).
Again in [5], it was shown that when p = 4m where m is a positive integer,
2
3 4 1
λp (TH ) ≤ p+ + . (4)
8 3 3
equation (4) implies that λ8 (TH ) ≤ 33. Moreover, using a computer routine that ex-
plores all possible colorings of a subgraph of TH with 109 vertices, authors in [5] found
that 33 colors were required for the subgraph for 8 distance coloring and this value
exactly coincides with the value obtained from the conjecture stated in equation (1)
as well as with the upper bound stated in equation (4). In this paper, we prove that
λ8 (TH ) ≥ 33. Since λ8 (TH ) ≤ 33 [5], we get λ8 (TH ) = 33, thus answering the
conjecture stated in equation (1) positively.
2 Problem statement and key ideas
Definition 1. A vertex with coordinates (i, j) in TH is said to be a right vertex, or xr if
it is connected to the vertex with coordinates (i + 1, j) by an edge.
A right vertex xr with coordinates (i, j) is adjacent to the vertices having coordinates
(i+1, j), (i, j +1) and (i, j −1) but not adjacent to the vertex with coordinates (i−1, j).
Definition 2. A vertex with coordinates (i, j) in TH is said to be a left vertex, or xl if it
is connected to the vertex with coordinates (i − 1, j) by an edge.
A left vertex xl with coordinates (i, j) is adjacent to the vertices having coordinates
(i − 1, j), (i, j + 1) and (i, j − 1) but not adjacent to the vertex with coordinates
(i + 1, j). In Fig. 2, a right and a left vertex in TH are shown.
Definition 3. A subgraph Dx2p (p ∈ N) of TH centered at vertex x ∈ V (TH ) is the
maximum ordered vertex induced subgraph of TH such that for each pair of vertices
u, v ∈ V (Dx2p ), d(u, v) ≤ 2p and for every vertex w ∈ V (Dx2p ), d(w, x) ≤ p.
In Fig. 3 different Dx2p in TH are shown.
Note that for any right vertex xr and left vertex xl , Dx2pr and Dx2pl are isomorphic. So
any property that holds for Dx2pr also holds for Dx2pl . Therefore, we will state and prove
our results for Dx2pr and these also hold for Dx2pl .
4 Sasthi C. Ghosh et al.
xl xr
Fig. 2: xr and xl are right and left vertices in TH .
x xr xl xr xr
a. Dx0 b. Dx2r c. Dx2l d. Dx4r e. Dx8r
Fig. 3: Different Dx2p .
Consider a right vertex xr and we assume the coordinates of xr are (0, 0). The
subgraph Dx16r is shown in Fig. 4. Note that there are 3j vertices which are at distance
j from xr , where 1 ≤ j ≤ 8. In Fig. 4, the 3j vertices are denoted as v1j , v2j , · · · , v3j
j
{vij } where 1 ≤ j ≤ 8. For 5 ≤ q ≤ 8,
[
where 1 ≤ j ≤ 8. We now define Fj =
1≤i≤3j
we define the following sets of vertices.
(
q {vlq : i ≤ l ≤ j} when i ≤ j
Vi−j = q q
Vi−3q ∪ V1−j when i > j
3 Results
Consider V 0 = V (Dx16r ) \ V (Dx8r ) = F5 ∪ F6 ∪ F7 ∪ F8 . In the following discussion,
we investigate how many times at maximum a color used in Dx8r can be reused in V 0
and where it can be reused in V 0 .
As |V (Dx8r )| = 1 + |F1 | + |F2 | + |F3 | + |F4 | = 31, we need 31 distinct colors to
color the vertices of Dx8r and hence λ8 (Dx8r ) ≥ 31. In Fig. 4, we denote the 3j colors of
the vertices in Fj as cj1 , cj2 , · · · , cj3j , where 1 ≤ j ≤ 4. It is evident that color c assigned
Proving a Conjecture on 8-Distance Coloring of the Infinite Hexagonal Grid 5
v18
8
v24 v17 v28
8 7
v23 v21 v16 v27 v38
8 7 6
v22 v20 v18 v15 v26 v37 v48
8 7 6 5
v21 v19 v17 v15 v14 (c41 ) v25 v36 v47 v58
6 5 4
v16 v14 v12 (c412 ) v13 (c31 ) v24 (c42 ) v35 v46 v57
8 7 4
v20 v18 v11 (c411 ) v93 (c39 ) v12 (c21 ) v23 (c32 ) v34 (c43 ) v45 v68
6 5
v15 v13 v62 (c26 ) v11 (c11 ) v22 (c22 ) v33 (c33 ) v56 v67
8 7 4
v19 v17 v10 (c410 ) v83 (c38 ) xr (0, 0)(c) v21 (c12 ) v44 (c44 ) v55 v78
6 5
v14 v12 v52 (c25 ) v31 (c13 ) v32 (c23 ) v43 (c34 ) v66 v77
8 7
v18 v16 v94 (c49 ) v73 (c37 ) v42 (c24 ) v53 (c35 ) v54 (c45 ) v65 v88
6 5
v13 v11 v84 (c48 ) v63 (c36 ) v64 (c46 ) v75 v76 v87
8 7 6 5
v17 v15 v12 v10 v74 (c47 ) v85 v86 v97 v98
8 7 6
v16 v14 v11 v95 v96 7
v10 8
v10
8 7 6 7 8
v15 v13 v10 v11 v11
8 7 8
v14 v12 v12
8
v13
Fig. 4: All the vertices v with 1 ≤ d(v, xr ) ≤ 8 and color of all the vertices u with
d(u, xr ) ≤ 4 (Color is mentioned within brackets next to the corresponding vertex).
6 Sasthi C. Ghosh et al.
to xr cannot be reused at all in V 0 due to the reuse distance. In subsequent Observations
we will state and prove how many times at most the colors cj1 , cj2 , · · · , cj3j can be reused
in V 0 and where they can be be reused to attain their maximum reusability.
Observation 1 Each color c1i with i ∈ {1, 2, 3} can be reused at most three times in
V 0 . For maximum reusability, each color c1i must be reused three times in F8 .
Proof. There are three vertices in F1 where the colors c1i with i ∈ {1, · · · , 3} are
used. We first consider the color c11 used in vertex v11 . Observe that c11 can be reused in
8 8 8 8
R = V5−17 = R1 ∪ R2 ∪ R3 where R1 = V5−8 , R2 = V9−12 and R3 = V13−17 are
three disjoint subsets of vertices. Note that every pair of vertices in R1 are at distance at
most 8, and the same is true for R2 and R3 . Hence c11 can be reused at most three times
in V 0 , once in R1 , once in R2 and once in R3 . Note that v11 and v31 are symmetric with
respect to xr where c11 and c13 are used respectively. Hence result obtained regarding
how many times the color c11 can be reused in V 0 also holds for c13 . So we are remaining
to consider the color c12 used in vertex v21 . For c12 , the corresponding sets R, R1 , R2 and
8 8 8 8
R3 can easily be obtained as R = V13−1 , R1 = V13−16 , R2 = V17−21 and R3 = V22−1
1 0
respectively. Hence c2 can also be reused at most three times in V .
It is evident that each c1i with i ∈ {1, 2, 3} can only be reused in F8 . Hence for
maximum reusability, each color c1i must be reused three times in F8 .
Observation 2 Each color c2i with i ∈ {1, · · · , 6} can be reused at most two times in
V 0 . For maximum reusability, each color c2i must be reused two times in F7 ∪ F8 .
Proof. There are six vertices in F2 where the colors c2i with i ∈ {1, · · · , 6} are used.
Observe that the vertices v12 and v42 are symmetric with respect to xr where c21 and c24
are used respectively. Similar fact holds for c22 and c23 ; c25 and c26 . Hence results obtained
regarding how many times the colors c21 , c22 and c25 can be reused in V 0 also hold for c24 ,
c23 and c26 respectively. Therefore we need to consider the colors c21 , c22 and c25 only.
– We will first consider the color c21 . It can be reused in R = V8−15
7 8
∪ V9−17 . Observe
7 8 7 8
that R = R1 ∪ R2 where R1 = V8−11 ∪ V9−12 and R2 = V12−15 ∪ V13−17
are two vertex disjoint subsets. Note that there does not exist any pair of vertices
in R1 at distance 9 or more. Same fact holds for R2 . Hence c21 can be reused at
most two times in V 0 , once in R1 and once in R2 . It is evident that each c2i with
i ∈ {1, · · · , 6} can only be reused in F7 ∪ F8 . Hence c21 must be reused two times
in F7 ∪ F8 to attain its maximum reusability. Similar result holds for c24 also.
For the colors c22 and c25 the sets R, R1 and R2 are stated below.
– c22 : R = V12−19
7 8
∪ V13−21 = R1 ∪ R2 ; R1 = V12−15 7 8
∪ V13−17 7
; R2 = V16−19 ∪
8
V18−21 .
– c25 : R = V1−8
7 8
∪ V1−9 = R1 ∪ R2 ; R1 = V1−4 7 8
∪ V1−4 7
; R2 = V5−8 8
∪ V5−9 .
Observation 3 Each color c3i with i ∈ {1, · · · , 9} can be reused at most three times
in V 0 . For maximum reusability, each c3i with i ∈ {2, 5, 8} must be reused at least two
times in F7 ∪ F8 and each c3i with i ∈ {1, · · · , 9} \ {2, 5, 8} must be reused at least
once in F7 ∪ F8 .
Proving a Conjecture on 8-Distance Coloring of the Infinite Hexagonal Grid 7
Proof. Note that the pair of colors c31 and c36 are assigned to the vertices v13 and v63 which
are symmetric with respect to xr . Similar fact holds for c32 and c35 ; c33 and c34 ; c39 and c37 .
Hence results obtained regarding how many times the colors c31 , c32 , c33 and c39 can be
reused in V 0 also hold for c36 , c35 , c34 and c37 respectively. Therefore, we need to consider
the colors c31 , c32 , c33 , c39 only. We will consider the case for the color c38 separately.
– First consider the color c31 . It can be reused in R = V7−13 6 7
∪ V8−15 8
∪ V5−18 =
7 8 6 7 8
R1 ∪ R2 ∪ R3 where R1 = V8−8 ∪ V5−9 , R2 = V7−10 ∪ V9−12 ∪ V10−13 and
6 7 8
R3 = V11−13 ∪ V13−15 ∪ V14−18 are three disjoint subsets of vertices. Observe that
every pair of vertices belonging to the same subset are at distance at most 8. Hence
c31 can be reused at most three times, once in R1 ⊂ F7 ∪ F8 , once in R2 and once
in R3 . To reuse c31 three times in V 0 , it must be reused at least once at F7 ∪ F8 .
Similar result holds for c36 also.
For each of the colors c32 , c33 , c39 and c38 the set R and its corresponding partitions
R1 , R2 , R3 are as stated below.
– c32 : R = V10−13
6 7
∪ V12−15 8
∪ V9−21 = R1 ∪ R2 ∪ R3 ; R1 = V9−12 8 6
; R2 = V10−13 ∪
7 8 8 3
V12−15 ∪ V13−16 ; R3 = V17−21 ; To reuse c2 three times, it must be used once in
R1 ⊂ F8 ⊂ F7 ∪ F8 , once in R2 and once in R3 ⊂ F8 ⊂ F7 ∪ F8 . Hence to reuse
c32 three times, it must be used at least two times in F7 ∪ F8 . Similar result holds
for c35 also.
– c33 : R = V10−16
6 7
∪V12−19 ∪V12−18
= R1 ∪R2 ∪R3 ; R1 = V10−126 7
∪V12−14 8
∪V12−16 ;
6 7 8 7 8 3
R2 = V13−16 ∪ V15−18 ∪ V17−20 ; R3 = V19−19 ∪ V21−1 ; To reuse c3 three times,
it must be used once in R1 , once in R2 and once in R3 ⊂ F7 ∪ F8 . Hence to reuse
c33 three times, it must be used at least once in F7 ∪ F8 . Similar result holds for c34
also.
– c39 : R = V4−10
6 7
∪ V5−12 ∪ V4−178
= R1 ∪ R2 ∪ R3 ; R1 = V4−6 6
∪ V5−77 8
∪ V4−8 ;
6 7 8 7 8 3
R2 = V7−10 ∪ V8−11 ∪ V9−12 ; R3 = V12−12 ∪ V13−17 ; To reuse c9 three times, it
must be used once in R1 , once in R2 and once in R3 ⊂ F7 ∪ F8 . Hence to reuse
c39 three times, it must be used at least once in F7 ∪ F8 . Similar result holds for c37
also.
– c38 : at R = V4−76
∪ V5−8 7
∪ V1−138
= R1 ∪ R2 ∪ R3 ; R1 = V1−4 8
; R2 = V4−7 6
∪
7 8 8 3
V5−8 ∪ V5−9 ; R3 = V10−13 ; To reuse c8 three times, it must be used once in
R1 ⊂ F8 ⊂ F7 ∪ F8 , once in R2 and once in R3 ⊂ F8 ⊂ F7 ∪ F8 . Hence to reuse
c38 three times, it must be used at least two times in F7 ∪ F8 .
Observation 4 Each color c4i with i ∈ {1, · · · , 12} can be reused at most three times
in V 0 . For maximum reusability, each c4i with i ∈ {1, · · · , 12} must be reused at least
two times in F7 ∪ F8 .
Proof. Note that the colors c41 and c47 are used at v14 and v74 respectively which are
symmetric with respect to xr . Similar fact also hold for c42 and c46 ; c43 and c45 ; c48 and c412 ;
c49 and c411 . Hence result obtained regarding how many times the colors c41 , c42 , c43 , c48
and c49 can be reused in V 0 are same for the colors c47 , c46 , c45 , c412 and c411 respectively.
Therefore we need to consider the colors c41 , c42 , c43 , c48 and c49 only. We will consider the
remaining two colors c44 and c410 separately.
– We first consider the color c41 . It can be reused at R = V6−11
5 6
∪ V7−13 7
∪ V7−16 ∪
8 5 6 7 8
V8−18 = R1 ∪ R2 ∪ R3 where R1 = V6−8 ∪ V7−9 ∪ V7−10 ∪ V8−11 , R2 =
8 Sasthi C. Ghosh et al.
5 6 7 8 7 8
V9−11 ∪ V10−13 ∪ V11−14 ∪ V12−16 and R3 = V15−16 ∪ V17−18 are three disjoint
subsets. Observe that every pair of vertices belonging to the same subset are at
distance at most 8. Hence c41 can be reused at most three times, once in R1 , once in
R2 and once in R3 .
Observe that c41 can be reused two times in F5 ∪ F6 only when c41 is used once
5 6 5 6
in u ∈ V6−8 ∪ V7−9 ⊂ R1 and once in v ∈ V9−11 ∪ V10−13 ⊂ R2 such that
d(u, v) ≥ 9. Note that for any such (u, v) pair, there does not exist any w ∈ R3
such that d(u, w) ≥ 9 and d(v, w) ≥ 9. That is, in that case, c41 cannot be reused
once more in R3 . This implies that for maximum reusability, c41 can be reused at
most once in F5 ∪ F6 . Hence c41 must be used at least two times in F7 ∪ F8 to attain
its maximum reusability. Similar result holds for c47 also.
For each of the colors c42 , c43 , c44 , c48 , c49 and c410 the set R and its corresponding
partitions R1 , R2 , R3 are stated below.
– c42 : R = V9−115 6
∪ V10−13 7
∪ V8−19 8
∪ V9−21 = R1 ∪ R2 ∪ R3 ;
7 8 5 6 7 8 7
R1 = V8−11 ∪ V9−12 ; R2 = V9−11 ∪ V10−13 ∪ V12−15 ∪ V13−17 ; R3 = V16−19 ∪
8
V18−21 ;
To reuse c42 three times, it must be reused once in R1 ⊂ F7 ∪ F8 , once in R2 and
once in R3 ⊂ F7 ∪ F8 and hence it must be reused at least two times in F7 ∪ F8 .
Similar result holds for c46 also.
– c43 : R = V9−145 6
∪ V10−16 7
∪ V11−20 8
∪ V12−22 = R1 ∪ R2 ∪ R3 ;
5 6 7 8 7 8 5
R1 = V9−11 ∪ V10−13 ∪ V11−14 ∪ V12−16 ; R2 = V15−16 ∪ V17−18 ; R3 = V12−14 ∪
6 7 8
V14−16 ∪ V17−20 ∪ V19−22 ;
Observe that c43 can be reused two times in F5 ∪ F6 only when c43 is used once
5 6 5 6
in u ∈ V9−11 ∪ V10−13 ⊂ R1 and once in v ∈ V12−14 ∪ V14−16 ⊂ R3 such that
d(u, v) ≥ 9. Note that for any such (u, v) pair, there does not exist any w ∈ R2
such that d(u, w) ≥ 9 and d(v, w) ≥ 9. That is, in that case, c43 cannot be reused
once more in R2 . This implies that for maximum reusability, c41 can be reused at
most once in F5 ∪ F6 . Hence c43 must be used at least two times in F7 ∪ F8 to attain
its maximum reusability. Similar result holds for c45 also.
– c44 : R = V11−14
5 6
∪ V13−16 7
∪ V12−1 8
∪ V13−1 = R1 ∪ R2 ∪ R3 .
7 8 5 6 7 8 7
R1 = V12−15 ∪ V13−17 ; R2 = V11−14 ∪ V13−16 ∪ V16−18 ∪ V18−20 ; R3 = V19−1 ∪
8
V21−1 ;
To reuse c44 three times, it must be reused once in R1 ⊂ F7 ∪ F8 , once in R2 and
once in R3 ⊂ F7 ∪ F8 and hence it must be reused at least two times in F7 ∪ F8 to
attain its maximum reusability.
– c48 : R = V1−4 5
∪ V1−46 7
∪ V19−8 8
∪ V21−9 = R1 ∪ R2 ∪ R3 ;
7 8 5 6 7 8 7 8
R1 = V19−1 ∪ V21−1 ; R2 = V1−4 ∪ V1−4 ∪ V2−4 ∪ V2−4 ; R3 = V5−8 ∪ V5−9 ;
4
To reuse c8 three times, it must be reused once in R1 ⊂ F7 ∪ F8 , once in R3 ⊂
F7 ∪ F8 and once in R2 and hence it must be reused at least two times in F7 ∪ F8
to attain its maximum reusability. Similar result holds for c412 also.
– c49 : R = V1−6 5
∪ V1−76 7
∪ V21−9 8
∪ V24−10 = R1 ∪ R2 ∪ R3 ;
5 6 7 8 7 8 5 6
R1 = V1−3 ∪ V1−3 ∪ V21−4 ∪ V24−3 ; R2 = V5−5 ∪ V4−5 ; R3 = V4−6 ∪ V4−7 ∪
7 8
V6−9 ∪ V6−10 ;
Observe that c49 can be reused two times in F5 ∪ F6 only when c49 is used once in
5 6 5 6
u ∈ V1−3 ∪ V1−3 ⊂ R1 and once in v ∈ V4−6 ∪ V4−7 ⊂ R3 such that d(u, v) ≥ 9.
Note that for any such (u, v) pair, there does not exist any w ∈ R2 such that
Proving a Conjecture on 8-Distance Coloring of the Infinite Hexagonal Grid 9
d(u, w) ≥ 9 and d(v, w) ≥ 9. That is, in that case, c49 cannot be reused once more
in R2 . This implies that for maximum reusability, c49 can be reused at most once in
F5 ∪F6 . Hence c49 must be used at least two times in F7 ∪F8 to attain its maximum
reusability. Similar result holds for c411 also.
– c410 : R = V4−6
5 6
∪ V4−7 7
∪ V1−12 8
∪ V1−13 = R1 ∪ R2 ∪ R3 ;
7 8 5 6 7 8 7 8
R1 = V1−4 ∪ V1−4 ; R2 = V4−6 ∪ V4−7 ∪ V5−8 ∪ V5−9 ; R3 = V9−12 ∪ V10−13 ;
4
To reuse c10 three times, it must be reused once in R1 ⊂ F7 ∪ F8 , once in R2 and
once in R3 ⊂ F7 ∪ F8 and hence it must be reused at least two times at F7 ∪ F8 .
Now we investigate whether the colors used in Dx8r are sufficient to color the ver-
tices of V 0 or new color/s is/are to be introduced to color them. Note that if new color/s
is/are necessary then the required number of new color/s will depend on the number
of vertices of V 0 which cannot be colored with the colors used in Dx8r and how many
times at maximum a new color can be used in V 0 . In following Observation, we first
state that how many times at maximum a color not appearing in Dx8r can be used in V 0
and then based on this result, in Theorem 1, we finally state the minimum number of
colors required to color the vertices of Dx16r .
Observation 5 A color cn not appearing in Dx8r can be used at most five times in V 0 .
Proof. The color cn can be used in V 0 = F5 ∪F6 ∪F7 ∪F8 = V1−24 8 7
∪V1−21 6
∪V1−18 ∪
5
V1−15 . Observe that V 0 can be partitioned into six disjoint subsets R1 = V21−1 8
∪
7 6 5 8 7 6 5 8
V19−1 ∪ V16−1 ∪ V14−1 , R2 = V17−20 ∪ V15−18 ∪ V13−15 ∪ V11−13 , R3 = V12−16 ∪
7 6 5 8 7 6 5 8 7
V11−14 ∪ V9−12 ∪ V8−10 , R4 = V7−11 ∪ V7−10 ∪ V5−8 ∪ V5−7 , R5 = V2−6 ∪ V2−5 ∪
6 5 7
V2−4 ∪ V2−4 and R6 = V6−6 where every pair of vertices in a subset is at most distance
8 apart. If cn is not used in v67 , the only vertex in R6 , then cn can be used at most
five times in V 0 . In other words, to use cn six times in V 0 , cn must be used in v67 .
If cn is used in v67 then the set of vertices where cn can be reused is R0 = V11−2 8
∪
7 6 5 0
V11−1 ∪ V9−1 ∪ V9−15 . Now observe that R can be partitioned into four disjoint subsets
R10 = V11−15
8 7
∪ V11−13 6
∪ V9−12 5
∪ V9−10 , R20 = V16−19
8 7
∪ V14−18 6
∪ V13−15 5
∪ V11−13 ,
0 8 7 6 5 0 8 7
R3 = V20−24 ∪ V19−21 ∪ V16−1 ∪ V14−15 and R4 = V1−2 ∪ V1−1 where every pair of
vertices in a subset is at most distance 8 apart. This implies that cn can be used at most
five times in V 0 regardless of whether cn is used or not used in v67 .
Now we state and prove our main theorem.
Theorem 1. λ8 (TH ) ≥ 33.
Proof. As |V (Dx8r )| = 31 and |V (Dx16r )| = 109, (109 − 31) = 78 vertices are to be
colored with the colors from cj1 , cj2 , · · · , cj3j , where 1 ≤ j ≤ 4 (Note that color c of xr
cannot be reused in Dx16r as any vertex in Dx16r is at distance at most 8 from xr ). From
Observation 1, Observation 2, Observation 3 and Observation 4, using these colors we
can color at most ( (3 × 3) + (6 × 2) + (9 × 3) + (12 × 3) ) = 84
| {z } | {z } | {z } | {z }
c1i ,i∈{1,2,3} c2i ,i∈{1,2,··· ,6} c3i ,i∈{1,2,··· ,9} c4i ,i∈{1,2,··· ,12}
vertices in V 0 if each of them are reused with their maximum potential of reusability.
As discussed in Observation 1, all c1i , i ∈ {1, 2, 3} must be reused three times in
F8 to attain their maximum reusability in V 0 ; Hence all c1i s, i ∈ {1, 2, 3} together must
10 Sasthi C. Ghosh et al.
occupy 9 vertices in F8 here. As discussed in Observations 2, all c2i , i ∈ {1, 2, · · · , 6}
must be reused two times in F7 ∪ F8 to attain their maximum reusability; Hence all
c2i s, i ∈ {1, 2, · · · , 6} together must occupy 12 vertices in F8 ∪ F7 here. As discussed
in Observations 3, each of c32 , c35 and c38 must be used at least two times in F7 ∪ F8 to
attain their maximum reusability and each of c3i , i ∈ {1, 2, · · · , 9} \ {2, 5, 8} must be
reused at least once in F7 ∪ F8 to attain their maximum reusability. So, all c3i s, i ∈
{1, 2, · · · , 9} together must occupy at least 12 vertices in F7 ∪ F8 here. As discussed in
Observations 4, all c4i , i ∈ {1, 2, · · · , 12} must be reused at least two times in F7 ∪F8 to
attain their maximum reusability. So, all c4i s, i ∈ {1, 2, · · · , 12} together must occupy at
least 24 vertices in F7 ∪ F8 here. Therefore, to satisfy the maximum reusability of each
color used in Dx8r , total positions required at F7 ∪ F8 is at least 9 + 12 + 12 + 24 = 57.
However, total positions available at F7 ∪ F8 is 21 + 24 = 45 only. Since two or more
colors cannot be given at the same vertex, these colors together must loose the potential
of maximum reusability by at least 57 − 45 = 12 in V 0 . Hence they together can color
maximum (84 − 12) = 72 vertices in V 0 . Since V 0 has 78 vertices, new color/s must be
needed to color at least (78 − 72) = 6 vertices of V 0 . From observation 5, a new color
can color at most five vertices in V 0 . So at least two new colors are required to color
these six vertices. Since 31 distinct colors are required for Dx8r , at least (31 + 2) = 33
colors are required for Dx16r . Hence λ8 (Dx16r ) ≥ 33.
As for any left vertex xl , Dx16r and Dx16l are isomorphic, so λ8 (Dx16l ) ≥ 33. As Dx16r
and Dx16l are subgraphs of TH , we conclude that λ8 (TH ) ≥ 33. Hence the proof.
4 Conclusion
In our work we show that λp (TH ) ≥ 33 and this exactly coincides with the value
obtained from the conjecture and upper bound of λp (TH ) as obtained in [5] when
p = 8. Exact value of λp (TH ) for even p > 8 is still unknown and determining it is an
interesting problem for future work.
References
1. W. K. Hale, Frequency assignment: Theory and applications, Proc. IEEE, 68 (1980),
pp.1497-1514.
2. G. Wegner, Graphs with given diameter and a colouring problem( Preprint, University of
Dortmund, 1977).
3. A. A. Bertossi, M. C. Pinotti, R. Rizzi and A. M. Shende, Channel assignment in honeycomb
networks, Theoretical Computer Science, vol. 2841, pp. 150-162, 2003.
4. A. A. Bertossi, M. C. Pinotti, R. Rizzi and A. M. Shende, Channel assignment for interfer-
ence avoidance in honeycomb wireless networks, Journal of Parallel and Distributed Com-
puting, vol. 64, pp. 1329-1344, 2004.
5. P. Jacko, S. Jendrol, Distance coloring of the hexagonal lattice, Discussiones Mathematicae
Graph Theory, vol. 25, pp. 151-166, 2005.
6. S. Nandi, N. Panigrahy, M. Agarwal, S. C. Ghosh and S. Das, Efficient assignment for cel-
lular networks modeled as honeycomb grid, Proceedings of the 15th Italian Conference on
Theoretical Computer Science, 2014, pp. 183-295.
Proving a Conjecture on 8-Distance Coloring of the Infinite Hexagonal Grid 11
7. F. Kramer, H. Kramer, A survey on the distance-colouring of graphs, Discrete Mathematics,
vol. 308(2-3), pp. 422-426, 2008.
8. Sandip Das, Sasthi C. Ghosh, Soumen Nandi, Sagnik Sen, A lower bound technique for radio
k-coloring, Discret. Math, vol.340(5), pp. 855-861, 2017.
9. Bostjan Bresar, Jasmina Ferme, Sandi Klavzar, Douglas F. Rall, A survey on packing color-
ings, Discuss. Math. Graph Theory vol. 40(4), pp. 923-970, 2020.
10. W. Goddard and H. Xu, A note on S-packing colorings of lattices, Discrete Applied Mathe-
matics, vol. 166, pp. 255-262, 2014.
11. N. Gastineau, H. Kheddouci and O. Togni, Subdivision into i-packings and S-packing chro-
matic number of some lattices, Ars Mathematica Contemporanea, vol. 9, pp. 321-344, 2015.