Given p 2 N, a p distance coloring is a coloring f : V ! f1; 2; ; ng 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 defined 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 Mathematicae Graph Theory, 2005] that p(TH ) = " 3 p + 4 2# where [x] 8 3 is an integer, x 2 R and x 1 < [x] x + 1 . In this paper, we prove that 2 2 8(TH ) = 33 which coincides with the conjectured value.
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 represented 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 coloring 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 ! f1; 2; ; ng 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 License Attribution 4.0 International (CC BY 4.0). 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 coloring 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.
(
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, p(TH ) = " 3 8 p + 4 2# 3 ([x] is an integer, x 2 R and x
It has been shown in [5] that
where T H0 (V 0; E0) is the maximum subgraph of TH such that d(u; v) 2p for every
pair of vertices u; v 2 V 0. Using equation (
+ 1:
p(TH )
equation (
Again in [5], it was shown that when p = 4m where m is a positive integer,
32 [5]. But this value is one less than that of the
equation (
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 2 N) of TH centered at vertex x 2 V (TH ) is the maximum ordered vertex induced subgraph of TH such that for each pair of vertices u; v 2 V (Dx2p), d(u; v) 2p and for every vertex w 2 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.
xl
xr
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 ; ; v3jj where 1 j 8. We now define Fj = [ fvij g where 1 j 8. For 5 q 8, 1 i 3j we define the following sets of vertices.
Viq j = (fvlq : i l
Viq 3q [ V1q j jg when i j when i > j 3
Results Consider V 0 = V (Dx16r) n 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 jV (Dx8r )j = 1 + jF1j + jF2j + jF3j + jF4j = 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 4 (Color is mentioned within brackets next to the corresponding vertex). d(u;xr) 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 ci1 with i 2 f1; 2; 3g can be reused at most three times in V 0. For maximum reusability, each color ci1 must be reused three times in F8. Proof. There are three vertices in F1 where the colors ci1 with i 2 f1; ; 3g are used. We first consider the color c11 used in vertex v11. Observe that c11 can be reused in R = V58 17 = R1 [ R2 [ R3 where R1 = V58 8, R2 = V98 12 and R3 = V183 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 R3 can easily be obtained as R = V183 1, R1 = V183 16, R2 = V187 21 and R3 = V282 1 respectively. Hence c12 can also be reused at most three times in V 0.
It is evident that each ci1 with i 2 f1; 2; 3g can only be reused in F8. Hence for maximum reusability, each color ci1 must be reused three times in F8. Observation 2 Each color ci2 with i 2 f1; ; 6g can be reused at most two times in V 0. For maximum reusability, each color ci2 must be reused two times in F7 [ F8. Proof. There are six vertices in F2 where the colors ci2 with i 2 f1; ; 6g 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 = V 7 8 15 [ V98 17. Observe that R = R1 [ R2 where R1 = V87 11 [ V98 12 and R2 = V172 15 [ V183 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 ci2 with i 2 f1; ; 6g 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 = V172 19 [ V183 21 = R1 [ R2; R1 = V172 15 [ V183 17; R2 = V176 19 [
V188 21.
– c52: R = V17 8 [ V18 9 = R1 [ R2; R1 = V17 4 [ V18 4; R2 = V57 8 [ V58 9. Observation 3 Each color ci3 with i 2 f1; ; 9g can be reused at most three times in V 0. For maximum reusability, each ci3 with i 2 f2; 5; 8g must be reused at least two times in F7 [ F8 and each ci3 with i 2 f1; ; 9g n f2; 5; 8g must be reused at least once in F7 [ F8. 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 c13, 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 = V76 13 [ V87 15 [ V58 18 = R1 [ R2 [ R3 where R1 = V87 8 [ V58 9, R2 = V76 10 [ V97 12 [ V180 13 and R3 = V161 13 [ V173 15 [ V184 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 c3, c33, c39 and c38 the set R and its corresponding partitions 2
R1, R2, R3 are as stated below. – c32: R = V160 13 [ V172 15 [ V 8 9 12; R2 = V160 13 [ 9 21 = R1 [ R2 [ R3; R1 = V 8 V172 15 [ V183 16; R3 = V187 21; To reuse c32 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 = V160 16 [V172 19 [V182 1 = R1 [R2 [R3; R1 = V160 12 [V172 14 [V182 16; R2 = V163 16 [ V175 18 [ V187 20; R3 = V179 19 [ V281 1; To reuse c33 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. – cR932: R= =V76V1460 [10V[87V1571 [12V[98V1428; 1R7 3==RV1172[ R122[[VR1833; 1R7;1T=o rVeu46se6 c[39 Vth57re7e [timVe48s, 8it; 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 = V 6 5 8 [ V18 13 = R1 [ R2 [ R3; R1 = V18 4; R2 = V 6 V57 8 [ V58 94; R73[=V 7V180 13; To reuse c38 three times, it must be used on4ce7 i[n 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 ci4 with i 2 f1; ; 12g can be reused at most three times in V 0. For maximum reusability, each ci4 with i 2 f1; ; 12g 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 c141. Hence result obtained regarding how many times the colors c4; c4; c4; c8 1 2 3 4 and c49 can be reused in V 0 are same for the colors c4; c46; c45; c412 and c141 respectively. 7 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.
– VW8e first consider the color c41. It can be reu6sed8 a[t RV76=9 V[65V1717 [10V[76 V1838 [11V, 77R126 =[ 8 18 = R1 [ R2 [ R3 where R1 = V 5
V 5
9 11 [ V160 13 [ V171 14 [ V182 16 and R3 = V175 16 [ V187 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 in u 2 V65 8 [ V76 9 R1 and once in v 2 V95 11 [ V160 13 R2 such that d(u; v) 9. Note that for any such (u; v) pair, there does not exist any w 2 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 c4, c4, c4, c48, c49 and c410 the set R and its corresponding 2 3 4 partitions R1, R2, R3 are stated below. – c42: R = V95 11 [ V160 13 [ V87 19 [ V98 21 = R1 [ R2 [ R3;
R1 = V 7 9 11 [ V160 13 [ V172 15 [ V183 17; R3 = V176 19 [ 8 11 [ V98 12; R2 = V 5 V188 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 = V 5
9 911 1[4V[160V16103 [16V[171V11714 [20V[182V11826; 2R22==RV1175[ R162[[VR1873; 18; R3 = V152 14 [ R1 = V 5 V164 16 [ V177 20 [ V189 22; Observe that c43 can be reused two times in F5 [ F6 only when c43 is used once in u 2 V95 11 [ V160 13 R1 and once in v 2 V152 14 [ V164 16 R3 such that d(u; v) 9. Note that for any such (u; v) pair, there does not exist any w 2 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. 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 = V 5 4 7 [ V174126[[VV186 13 = R1 [ R2 [ R3;
R1 = V17 44[6V[18 V4;6R2 = V 5 4 7 [ V57 8 [ V58 9; R3 = V97 12 [ V180 13; To reuse c410 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 vertices 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. VP1r5oo1f5.. TOhbesecrovloertchnatcaVn0bceaunsebde inpaVrt0it=ionFed5[inFto6 [siFx7d[isFjo8in=t sVu18bs2e4ts[ RV117 2=1 [VV28116 118 [[ V179 1 [ V166 1 [ V154 1, R2 = V187 20 [ V175 18 [ V163 15 [ V151 13, R3 = V182 16 [ VV12761 41[4 V[25V946 a1n2d[RV685=1V0,67R64 w=heVr7e8 e1v1e[ryVp7a7ir1o0f[veVr5t6ic8es[inV5a5s7u,bRse5t i=saVt 2m8o6s[tdVis27tan5c[e 8 apart. If cn is not used in v67, the only vertex in R6, then cn can be used at most 7 five times in V 0. In other words, to use cn six times in V 0, cn must be used in v6 . If cn is used in v67 then the set of vertices where cn can be reused is R0 = V181 2 [ V171 1 [ V96 1 [ V95 15. Now observe that R0 can be partitioned into four disjoint subsets R10 = V181 15 [ V171 13 [ V 6 9 10, R20 = V186 19 [ V174 18 [ V163 15 [ V151 13, 9 12 [ V 5 R30 = V280 24 [ V179 21 [ V166 1 [ V154 15 and R40 = V 8 1 1 where every pair of 1 2 [ V 7 vertices in a subset is at most distance 8 apart. This implies that cn can be used at most 7 five times in V 0 regardless of whether cn is used or not used in v6 .
Now we state and prove our main theorem.
Theorem 1.
8(TH )
Proof. As jV (Dx8r )j = 31 and jV (Dx16r)j = 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 ci1|;i2{fz1;2};3g ci2;i|2f1{;z2; } ;6g ci3;i|2f1{;z2; } ;9g ci4;i|2f1{;2z; };12g vertices in V 0 if each of them are reused with their maximum potential of reusability.
As discussed in Observation 1, all ci1; i 2 f1; 2; 3g must be reused three times in F8 to attain their maximum reusability in V 0; Hence all ci1s, i 2 f1; 2; 3g together must occupy 9 vertices in F8 here. As discussed in Observations 2, all ci2; i 2 f1; 2; ; 6g must be reused two times in F7 [ F8 to attain their maximum reusability; Hence all ci2s, i 2 f1; 2; ; 6g 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 ci3; i 2 f1; 2; ; 9g n f2; 5; 8g must be reused at least once in F7 [ F8 to attain their maximum reusability. So, all ci3s, i 2 f1; 2; ; 9g together must occupy at least 12 vertices in F7 [ F8 here. As discussed in Observations 4, all ci4; i 2 f1; 2; ; 12g must be reused at least two times in F7 [F8 to attain their maximum reusability. So, all ci4s, i 2 f1; 2; ; 12g 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.