Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 6s (2024) https://internationalpubls.com 259 Prime Graceful Chromatic Number of Diverse Graphs M. Keerthika 1 , V. Kowsalya2 1 Research Scholar, PG & Research Department of Mathematics, Sri Ramakrishna College of Arts & Science (Autonomous), Coimbatore, Tamil Nadu. (E-mail: keerthika.m@srcas.ac.in) 2Associate Professor, PG & Research Department of Mathematics, Sri Ramakrishna College of Arts & Science (Autonomous), Coimbatore, Tamil Nadu. (E-mail: kowsalya@srcas.ac.in) Article History: Received: 03-06-2024 Revised: 05-07-2024 Accepted: 25-07-2024 Abstract: In this paper, prime graceful coloring is introduced which aims to incorporate principles of prime and graceful coloring. The prime graceful coloring of star, path, cycle, friendship, pan and bistar graphs are proposed. This new approach is related to the prime graceful chromatic number which represent the fewest colors needed to color any graph adhering to the principles of prime graceful coloring. Also, the efficiency of new coloring are analyzed with the examples. Keywords: Prime Coloring, Graceful Coloring, Prime Graceful Labeling, Prime Graceful Coloring. 1. Introduction Let G be a finite simple undirected graph. Graph labeling technique was first developed by Rosa [5] who also provided numerous graph labeling techniques and Gallian J.A [2] conducted the survey on graph labeling. The proper coloring is alluded from [10]. Roger Entringer defined prime labeling and it is introduced by Tout et.all [9] and [3] gave the precise value of prime chromatic number of several graphs. Zhenming Bi et.all [1,11] introduced the concept of graceful colorings of graphs and the graceful chromatic number for wheel graph family are shown to be graceful [8]. In 2018, Selvarajan.T.M, Subramoniam.R [7] combined the characteristics of prime and graceful labeling and introduced a new labeling technique Prime Graceful Labeling and demonstrated the existence of prime graceful labeling in some graphs. Sayan Panma and Penying Rochanakul [6] defined prime-graceful number and applied prime graceful labeling to certain graphs, then Nandhini.S.P and Pooja Lakshmi.B [4] generalized the cardinality of the edges for the triangular snake graph. In this paper, we define the new technique Prime Graceful Coloring and its chromatic number are analyzed for some graphs. 2. Preliminaries Definition: 2.1[3] Prime Coloring is defined as G be a loop less and without multiple edges with p distinct vertices ꞷ:V(G)→{1, 2, …p},if each edge e =cicj, i≠j, gcd {ꞷ (vi), ꞷ (vj)} = 1, ꞷ (vi), ꞷ (vj) receives distinct colors. It is denoted by η(G). Definition: 2.2[8] A graceful k-coloring of a non-empty graph G=(V,E) is a proper vertex coloring ꞷ:V(G)→{1, 2, …k}, k ≥2 which induces a proper edge coloring ꞷ ∗: E(G)→{1,2,…k-1} defined by ꞷ ∗(𝑣𝑖 , 𝑣𝑗 ) = |ꞷ( 𝑣𝑖 ) - ꞷ( 𝑣𝑗)| where 𝑣𝑖 , 𝑣𝑗∈ V(G). The minimum k for which G has a graceful k-coloring is called graceful chromatic number χg(G). Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 6s (2024) https://internationalpubls.com 260 Definition: 2.3 [4] A graph G with p vertices and q edges is referred to have prime graceful labeling if the map depicts a one to one function ꞷ:V(G)→{1, 2, …k}. In this instance, k = min {p, q} such that GCD (ꞷ( 𝑣𝑖 ), ꞷ( 𝑣𝑗)) = 1 and the map reflect the induced one to one function ꞷ ∗: E(G)→{1,2,…k-1} defined by ꞷ ∗(𝑣𝑖𝑣𝑗 ) = |ꞷ( 𝑣𝑖 )- ꞷ( 𝑣𝑗)| such that the corresponding edge labels are distinct. Definition: 2.4 A prime graceful k-coloring of non-empty simple graph G is a proper vertex coloring ꞷ:V(G)→{1, 2,3……k} such that GCD (ꞷ(vi), ꞷ(vj)) = 1 where k ≥2 bring about a proper edge coloring ꞷ ∗:E(G)→ {1,2,3…k-1}defined by ꞷ ∗(vivj) = |ꞷ(vi)- ꞷ(vj)|, Ɐ k∈N the least k for which G exhibits prime graceful k-coloring is known as the chromatic number of prime graceful coloring. It is denoted by χpg(G). 3. Main Results Theorem: 3.1 Let K1,n be a star graph, then χpg(K1,n)= n+1. Proof: Let V (K1,n) = { vi : 1 ≤ i ≤ n+1} and E (K1,n) = {vivi+1 ∶ 1 ≤ i ≤ n}. Let ꞷ:V(K1,n)→{c1, c2, …,cn+1}where the vertex of degree n is designated as c1 (i.e),ꞷ(v1) = c1 and n-pendant vertices are designated as ꞷ( vi)= ci which satisfy GCD (ꞷ(v1), ꞷ(vi)) = 1 for 2 ≤ i ≤ n +1. Hence, adjacent vertices receive distinct colors. Let ꞷ*:E(K1,n)→{c1, c2, …,cn. For 2 ≤ i ≤ n+1, ꞷ*(v1vi) = ci-1 . It is determined by ꞷ ∗ (v1vi)= | ꞷ ( v1 ) - ꞷ ( 𝑣𝑖)| = ci-1. Consequently, ꞷ*(v1vi) receives distinct colors. We proved that χpg(K1,n) ≤ n + 1. To prove χpg(K1,n) ≥ n + 1, let us assume that χpg(K1,n) < n + 1, say n. We define proper vertex coloring of K1,n is ꞷ(v1) =c1, ꞷ( vi)=ci-1 Ɐ 2 ≤ i ≤ n+1. Then, it induces edge coloring ꞷ ∗ (v1v2)= 𝑐1, ꞷ ∗ (v1v3)= 𝑐1, ꞷ ∗ (v1v4)= c2, ꞷ ∗ (v1v5)= c3 and so on which is a contradiction with the definition of prime graceful coloring since the color of any two adjacent edges are distinct. Thus, χpg(K1,n) ≥ n + 1. Therefore, χpg(K1,n)= n+1. Figure 1 Analytical Evaluation of the 𝐾1,5 Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 6s (2024) https://internationalpubls.com 261 Theorem: 3.2 Let 𝑛 ≥ 5 be a positive integer, then χpg(𝑃𝑛)= 4. Proof: Define a proper vertex coloring ꞷ:V(Pn ) →{c1, c2, c3, c4}for 1≤ i ≤ n ꞷ(vi) = { 𝑐1, for i ≡ 0 mod 3 𝑐2, for 𝑣1 𝑐3, for i ≡ 2 mod 3 𝑐4, for i ≡ 1 mod 3, i ≠ 1 It is clear that GCD (ꞷ(vi), ꞷ(vi+1)) = 1. It induce a proper edge coloring ꞷ*:E(Pn)→{c1, c2 ,c3} as follows: ꞷ* (vivi+1) ={ 𝑐1, for i ≡ 1 mod 3 𝑐2, for i ≡ 2 mod 3 𝑐3, for i ≡ 0 mod 3 It satisfy ꞷ ∗ (vivi+1)= | ꞷ ( vi ) - ꞷ ( vi+1)| = c2 − c3 = c3 − c1 = c1 − c4 = c4 − c3 = c1, c2 , c3 , c1 Hence, adjacent vertices and edges receive distinct colors. Thus, χpg(Pn )≤4, for n ≥ 5 . To prove χpg(Pn)≥ 4, let us assume that χpg(Pn)< 4, say 3. We define vertex coloring of P5 is c2, c1, c3, c2, c1. Then, ꞷ ∗ (v1v2) = 𝑐1 , ꞷ ∗ (v2v3) = 𝑐2 , ꞷ ∗ (v3v4) = 𝑐1 , ꞷ ∗ (v4v5) = 𝑐1 which is a contradiction with the definition of prime graceful coloring since the color of any two adjacent edges are distinct. Thus, χpg(Pn)≥ 4. Therefore, χpg(Pn)= 4, if n ≥ 5. Corollary: 3.3 For any path, χpg(Pn)= 2, if n = 2. Corollary: 3.4 For any path, χpg(Pn)= 3, if n = 3 and 4. Figure 2 Analytical Evaluation of the 𝑃7 Theorem: 3.5 Let n ≥ 5 be a positive integer, then χpg(Cn)= 5. Proof: The vertices and edges of Cn are V (Cn) ={ vi :1 ≤ i ≤ n} and E(Cn)={vivi+1: 1 ≤ i ≤ n}. Case 1: n ≠ 3m+3, m∈N Define a proper vertex coloring ꞷ:V(Cn ) →{c1, c2, c3, c4, c5}as follows: For 1≤ i ≤ n ꞷ(vi) = { 𝑐1, for 𝑣2 𝑐2, for i ≡ 0 mod 3 𝑐3, for i ≡ 2 mod 3 and i ≠ 2 𝑐4, for 𝑣1 𝑐5, for i ≡ 1 mod 3 and i ≠ 1 Such that GCD (ꞷ(vi), ꞷ(vi+1)) = 1. It induce a proper edge coloring ꞷ*:E(Cn)→{c1, c2, c3} as follows: Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 6s (2024) https://internationalpubls.com 262 ꞷ* (vivi+1) ={ 𝑐3, for 𝑣1𝑣2 𝑎𝑛𝑑 i ≡ 0 mod 3 𝑐2, for i ≡ 1 mod 3 and i ≠ 1 𝑐1, for 𝑣𝑛𝑣1 and i ≡ 2 mod 3 It satisfy ꞷ ∗ (v1v2)= | ꞷ ( v1 ) - ꞷ ( 𝑣2)| = 𝑐4 − 𝑐1 = 𝑐3 ꞷ ∗ (v2v3)= | ꞷ ( v2 ) - ꞷ ( 𝑣3)| = 𝑐1 − 𝑐2 = 𝑐1 ꞷ ∗ (v3v4)= | ꞷ ( v3 ) - ꞷ ( 𝑣4)| = 𝑐2 − 𝑐5 = 𝑐3 ꞷ ∗ (v4v5)= | ꞷ ( v4 ) - ꞷ ( 𝑣5)| = 𝑐5 − 𝑐3 = 𝑐2 Hence, adjacent vertices and edges receive distinct colors. Thus, χpg(Cn)≤5. To prove χpg(Cn)≥ 5, let us assume that χpg(Cn)< 5, say 4. We define vertex coloring of C5 is c4, c1, c2, c3, c1. Then, ꞷ ∗ (v1v2)= 𝑐3, ꞷ ∗ (v2v3)= 𝑐1, ꞷ ∗ (v3v4)= 𝑐1, ꞷ ∗ (v4v5)= 𝑐2, ꞷ ∗ (v5v1) = 𝑐3 . Since ꞷ ∗ (v2v3) = 𝑐1 and ꞷ ∗ (v3v4) = 𝑐1 receives same color which is a contradiction with the definition of prime graceful coloring since the color of any two adjacent edges are distinct. Thus, χpg(Cn)≥ 5. Therefore, χpg(Cn)= 5 for n ≠3m+3, m∈N. Case 2: n = 3m + 3 Define a proper vertex coloring ꞷ:V(Cn ) →{c1, c2, c3, c4, c5}as follows: For 1≤ i ≤ n ꞷ(vi) = { 𝑐1, for 𝑣2 𝑐2, for i ≡ 1 mod 3 and i ≠ 1 𝑐3, for i ≡ 2 mod 3 and i ≠ 2 𝑐4, for 𝑣1 𝑐5, for i ≡ 0 mod 3 Such that GCD (ꞷ(vi), ꞷ(vi+1)) = 1. It induce a proper edge coloring ꞷ*:E(Cn)→{c1, c2, c3} as follows: ꞷ* (vivi+1) = { 𝑐1, for 𝑣𝑛𝑣1, i ≡ 1 mod 3 and i ≠ 1 𝑐2, for i ≡ 2 mod 3 and i ≠ 2 𝑐3, for 𝑣1𝑣2 𝑎𝑛𝑑 i ≡ 0 mod 3 𝑐4, for 𝑣2𝑣3 It satisfy ꞷ ∗ (v1v2)= | ꞷ ( v1 ) - ꞷ ( 𝑣2)| = 𝑐4 − 𝑐1 = 𝑐3 ꞷ ∗ (v2v3)= | ꞷ ( v2 ) - ꞷ ( 𝑣3)| = 𝑐1 − 𝑐5 = 𝑐4 ꞷ ∗ (v3v4)= | ꞷ ( v3 ) - ꞷ ( 𝑣4)| = 𝑐5 − 𝑐2 = 𝑐3 ꞷ ∗ (v4v5)= | ꞷ ( v4 ) - ꞷ ( 𝑣5)| = 𝑐2 − 𝑐3 = 𝑐1 Hence, adjacent vertices and edges receive distinct colors. Thus, χpg(Cn)≤5. To prove χpg(Cn)≥ 5, let us assume that χpg(Cn)< 5, say 4. We define vertex coloring of C6 is c4, c1, c2, c4, c3, c2. Then, ꞷ ∗ (v1v2) = 𝑐3 , ꞷ ∗ (v2v3) = 𝑐1 , ꞷ ∗ (v3v4) = 𝑐2 , ꞷ ∗ (v4v5) = 𝑐1 , ꞷ ∗ (v5v6) = 𝑐1 and ꞷ ∗ (v6v1) = 𝑐2 . Since ꞷ ∗ (v4v5) = 𝑐1 and ꞷ ∗ (v5v6) = 𝑐1 receives same color which is a contradiction with the definition of prime graceful coloring since the color of any two adjacent edges are distinct. Thus, χpg(Cn)≥ 5. Therefore, χpg(Cn)= 5 for n =3m+3, m∈N. Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 6s (2024) https://internationalpubls.com 263 Figure 3 Analytical Evaluation of the 𝐶6 Theorem: 3.6 Let Fn be a friendship graph, then for n ≥ 2 χpg(Fn)= 2n+1. Proof: The vertices and edges of Fn are V (Fn) = { vi : 1 ≤ i ≤ 2n+1} and E (Fn) = {vivi+1 ∶ 1 ≤ i ≤ 3n}. Let ꞷ:V(Fn)→{c1, c2, …,c2n+1}be a proper vertex coloring of Fn. It is defined as ꞷ(v1) =c1 (i.e), vertex of degree 2n, ꞷ( v2i)= c2i ∀ 1 ≤ i ≤ n. For i=1, ꞷ( v2i+1)= c2n+1 and ꞷ( v2i+1)= c2i-1 ∀ 2 ≤ i ≤ n. Since these colors are consecutive colors, GCD(ꞷ(v1),ꞷ(v2i)) =1, GCD (ꞷ(v1), ꞷ(v2i+1)) = 1 and GCD (ꞷ(v2i), ꞷ(v2i+1)) = 1 Let ꞷ*:E(Fn)→{c1, c2, …,c2n} be a proper edge coloring of Fn . It is defined as, ꞷ ∗ (vivi+1)= | ꞷ ( vi ) - ꞷ ( vi+1)| ∀ 1 ≤ i ≤ n. ꞷ*(v1v2i) = c2i-1 , ꞷ*(v1v2i+1) = c2i For i=1, ꞷ*(v2iv2i+1) = c2n-1 and for i≠1, ꞷ*(v2iv2i+1) = c1. Consequently, ꞷ*(vivi+1) receives distinct colors. Thus, χpg(Fn)≤2n + 1. To prove χpg(Fn)≥ 2n + 1, let us assume that χpg(Fn)< 2n + 1, say 2n. We must assign 2n colors for {v2i , v2i+1: 1 ≤ i ≤ n} for proper vertex coloring. Since one vertex is adjacent to remaining vertices, we cannot assign the same color which is a contradiction with the definition of prime graceful coloring since the color of any two adjacent vertices are distinct. Thus, χpg(Fn)≥ 2n + 1. Therefore, χpg(Fn)= 2n+1. Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 6s (2024) https://internationalpubls.com 264 Figure 4 Analytical Evaluation of the 𝐹4 Theorem: 3.7 Let n ≥ 3 be a positive integer, then χpg(n-pan graph)= { 4, if n = 3 5, if n ≠ 3 Proof: The vertices and edges of pan graph are V ( G ) = { vi :1 ≤ i ≤ n + 1} and E(G)={vivi+1: 1 ≤ i ≤ n + 1}. Case 1: n =3 Define a proper vertex coloring ꞷ:V(G ) →{c1, c2, c3, c4}as follows: For 1≤ i ≤ n+1, Such that GCD (ꞷ(vi), ꞷ(vi+1)) = 1. It induce a proper edge coloring ꞷ*:E(G)→{c1, c2, c3} as follows: ꞷ(vi) = { 𝑐1, for 𝑣2 𝑐2, for 𝑣4 𝑐3, for 𝑣1 𝑐4, for 𝑣3 ꞷ* (vivi+1) ={ c2, for v1v2 c3, for v2v3 c1, for v3v1 and v1v4 Hence, adjacent vertices and edges receive distinct colors. Therefore, χpg(n-pan graph)= 4 for n=3 Case 2: n ≠ 3m+3, m∈N Define a proper vertex coloring ꞷ:V(G ) →{c1, c2, c3, c4, c5}as follows: For 1≤ i ≤ n+1 ꞷ(vi) = { 𝑐1, for 𝑣2 𝑐2, for i ≡ 0 mod 3 𝑐3, for i ≡ 2 mod 3 , vn+1 and i ≠ 2 𝑐4, for 𝑣1 𝑐5, for i ≡ 1 mod 3 and i ≠ 1 Such that GCD (ꞷ(vi), ꞷ(vi+1)) = 1. It induce a proper edge coloring ꞷ*:E(G)→{c1, c2, c3} as follows: ꞷ* (vivi+1) = { 𝑐1, for i ≡ 2 mod 3 and vnv1 𝑐2, for i ≡ 1 mod 3 , v2vn+1 and i ≠ 1 𝑐3, for 𝑣1𝑣2 𝑎𝑛𝑑 i ≡ 0 mod 3 Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 6s (2024) https://internationalpubls.com 265 It satisfy ꞷ ∗ (vivi+1)= | ꞷ ( vi ) - ꞷ ( 𝑣𝑖+1)| Hence, adjacent vertices and edges receive distinct colors. Thus, χpg(n-pan graph)≤5. To prove χpg(n-pan graph)≥ 5, let us assume that χpg(Cn )< 5, say 4 . We define vertex coloring as c4, c1, c2, c3, c1 for 5-pan graph and the vertex with degree 1 is assigned with the color c3. Then, ꞷ ∗ (v1v2) = 𝑐3 , ꞷ ∗ (v2v3) = 𝑐1 , ꞷ ∗ (v2v6) = 𝑐2, ꞷ ∗ (v3v4) = 𝑐1 , ꞷ ∗ (v4v5) = 𝑐2 , ꞷ ∗ (v5v1) = 𝑐3 . Since ꞷ ∗ (v2v3) = 𝑐1 and ꞷ ∗ (v3v4) = 𝑐1 receives same color which is a contradiction with the definition of prime graceful coloring since the color of any two adjacent edges are distinct. Thus, χpg(n-pan graph)≥ 5. Therefore, χpg(n-pan graph)= 5 for n ≠3m+3, m∈N. Case 3: n = 3m + 3 Define a proper vertex coloring ꞷ:V(G ) →{c1, c2, c3, c4, c5}as follows: For 1≤ i ≤ n+1, Such that GCD (ꞷ(vi), ꞷ(vi+1)) = 1. It induce a proper edge coloring ꞷ*:E(G)→{c1, c2, c3} as follows: ꞷ(vi) = { 𝑐1, for 𝑣2 𝑐2, for i ≡ 1 mod 3 and i ≠ 1 𝑐3, for i ≡ 2 mod 3, vn+1 and i ≠ 2 𝑐4, for 𝑣1 𝑐5, for i ≡ 0 mod 3 ꞷ* (vivi+1) = { 𝑐4, for 𝑣2𝑣3 𝑐3, for 𝑣1𝑣2 𝑎𝑛𝑑 i ≡ 0 mod 3 𝑐2, for i ≡ 2 mod 3, v2vn+1 and i ≠ 2 𝑐1, for vnv1 , i ≡ 1 mod 3 and i ≠ 1 It satisfy ꞷ ∗ (vivi+1)= | ꞷ ( vi ) - ꞷ ( 𝑣𝑖+1)| Hence, adjacent vertices and edges receive distinct colors. Thus, χpg(n-pan graph)≤5. To prove χpg(n- pan graph)≥ 5, let us assume that χpg(n-pan graph)< 5, say 4. We define vertex coloring as c4, c1, c2, c3, c1, c3 for 6-pan graph and the vertex with degree 1 is assigned with the color c3. Then, ꞷ ∗ (v1v2)= 𝑐3 , ꞷ ∗ (v2v3) = 𝑐1 , ꞷ ∗ (v2v6) = 𝑐2, ꞷ ∗ (v3v4) = 𝑐1 , ꞷ ∗ (v4v5) = 𝑐2 , ꞷ ∗ (v5v6) = 𝑐2,ꞷ ∗ (v6v1) = 𝑐1 . Since ꞷ ∗ (v2v3) = 𝑐1 and ꞷ ∗ (v3v4) = 𝑐1 receive same color which is a contradiction with the definition of prime graceful coloring since the color of any two adjacent edges are distinct. Thus, χpg(n- pan graph)≥ 5. Therefore, χpg(n-pan graph)= 5 for n =3m+3, m∈N. Figure 5 Analytical Evaluation of the 5 - Pan graph Theorem: 3.8 Let Bn,n be a bistar graph, then χpg(Bn,n )={ n + 2, when n is odd n + 3, when n is even n + 4, when n ≡ 1 mod 6 and n ≠ 1 n + 5, when n ≡ 0 mod 6 Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 6s (2024) https://internationalpubls.com 266 Proof: The Bistar graph has 2n+2 vertices and 2n+1 edges. Case 1: n is odd Let V (Bn,n) = { ui :1 ≤ i ≤ n + 1} ∪ { vi :1 ≤ i ≤ n + 1}. Define a proper vertex coloring ꞷ:V(Bn,n ) →{c1, c2 , c3 …… cn+2}. ꞷ(u1) = c1 and ꞷ( v1)= cn+2 and ꞷ(ui) = ci , ꞷ(vi) = ci Ɐ 2 ≤ i ≤ n + 1. Such that GCD ꞷ(u1, ui) = 1, GCD ꞷ(v1, vi) = 1 and GCD ꞷ(u1, v1) = 1. Define a proper edge coloring ꞷ*:E(Bn,n)→{ c1, c2 , c3 …… cn+1} ꞷ ∗ (u1v1)= c1 − cn+2 = cn+1, ꞷ ∗ (u1ui)= c1 − ci = ci−1, ꞷ ∗ (v1vi)= cn+2 − ci = cn+2−i Hence, adjacent vertices and edges receive distinct colors. We proved that χpg(Bn,n) ≤ n + 2. To prove χpg(Bn,n) ≥ n + 2, let us assume that χpg(Bn,n) < n + 2 say n + 1. We define proper vertex coloring of Bn,n is ꞷ(ui) =ci, ꞷ( vi)=ci Ɐ 2 ≤ i ≤ n+1 since ꞷ(u1) and ꞷ( v1) are adjacent vertices we cannot assign the same color c1 which is a contradiction with the definition of prime graceful coloring since the color of any two adjacent vertices are distinct. Thus, χpg(Bn,n) ≥ n + 2. Therefore, χpg(Bn,n)= n+ 2 when n is odd. Case 2: n is even Let V (Bn,n) = { ui :1 ≤ i ≤ n + 1} ∪ { vi :1 ≤ i ≤ n + 1}. Define a proper vertex coloring ꞷ:V(Bn,n ) →{c1, c2 , c3 …… cn+3}. ꞷ(u1) = c1 and ꞷ( v1)= cn+3 And ꞷ(ui) = ci , ꞷ(vi) = ci+1 Ɐ 2 ≤ i ≤ n + 1. Such that GCD ꞷ(u1, ui) = 1, GCD ꞷ(v1, vi) = 1 and GCD ꞷ(u1, v1) = 1. Define a proper edge coloring ꞷ*:E(Bn,n)→{ c1, c2 , c3 …… cn+2} ꞷ ∗ (u1v1)= c1 − cn+3 = cn+2, ꞷ ∗ (u1ui)= c1 − ci = ci−1, ꞷ ∗ (v1vi)= cn+3 − ci+1 = cn+2−i Hence, adjacent vertices and edges receive distinct colors. We proved that χpg(Bn,n) ≤ n + 3. To prove χpg(Bn,n) ≥ n + 3, let us assume that χpg(Bn,n) < n + 3 say n + 2. We define proper vertex coloring of Bn,n is ꞷ(u1) = c1, ꞷ(ui) =ci, ꞷ( vi)=ci Ɐ 2 ≤ i ≤ n+1 and ꞷ( v1)= cn+2. Since v1 is adjacent to vi Ɐ 2 ≤ i ≤ n+1 for each edge vivj GCD ꞷ(v1, vi) ≠ 1 . Thus, χpg(Bn,n) ≥ n + 3. Therefore, χpg(Bn,n)= n+ 3 when n is even. Case 3: n ≡ 1 mod 6 and n ≠ 1 Let V (Bn,n) = { ui :1 ≤ i ≤ n + 1} ∪ { vi :1 ≤ i ≤ n + 1}. Define a proper vertex coloring ꞷ:V(Bn,n ) →{c1, c2,…… cn+4}. ꞷ(u1) = c1 and ꞷ( v1)= cn+4 ꞷ(ui) = ci , ꞷ(vi) = ci+2 Ɐ 2 ≤ i ≤ n + 1. Such that GCD ꞷ(u1, ui) = 1, GCD ꞷ(v1, vi) = 1 and GCD ꞷ(u1, v1) = 1. Define a proper edge coloring ꞷ*:E(Bn,n)→{ c1, c2 , c3 …… cn+3} ꞷ ∗ (u1v1)= c1 − cn+4 = cn+3, ꞷ ∗ (u1ui)= c1 − ci = ci−1, ꞷ ∗ (v1vi)= cn+4 − ci +2 = cn+2−i Hence, adjacent vertices and edges receive distinct colors. We proved that χpg(Bn,n) ≤ n + 4. To prove χpg(Bn,n) ≥ n + 4, let us assume that χpg(Bn,n) < n + 4 say n + 3. We define proper vertex coloring of Bn,n is ꞷ(u1) = c1, ꞷ(ui) =ci, ꞷ( vi)=ci Ɐ 2 ≤ i ≤ n+1 and ꞷ( v1)= cn+3. Since v1 is adjacent to vi Ɐ 2 ≤ i ≤ n+1 for each edge vivj GCD ꞷ(v1, vi) ≠ 1 . Thus, χpg(Bn,n) ≥ n + 4. Therefore, χpg(Bn,n)= n+ 4 when n ≡ 1 mod 6 and n ≠ 1. Case 4: n ≡ 0 mod 6 Let V (Bn,n) = { ui :1 ≤ i ≤ n + 1} ∪ { vi :1 ≤ i ≤ n + 1}. Define a proper vertex coloring ꞷ:V(Bn,n ) →{c1, c2 , c3 …… cn+5}. ꞷ(u1) = c1 and ꞷ( v1)= cn+5 and ꞷ(ui) = ci , ꞷ(vi) = ci+3 Ɐ 2 ≤ i ≤ n + 1. Such that GCD ꞷ(u1, ui) = 1, GCD ꞷ(v1, vi) = 1 and GCD ꞷ(u1, v1) = 1. Define a proper edge coloring ꞷ*:E(Bn,n)→{ c1, c2 , c3 …… cn+4} ꞷ ∗ (u1v1)= c1 − cn+5 = cn+4, ꞷ ∗ (u1ui)= c1 − ci = ci−1, ꞷ ∗ (v1vi)= cn+5 − ci +3 = cn+2−i Hence, adjacent vertices and edges receive distinct colors. We proved that χpg(Bn,n) ≤ n + 5. To prove χpg(Bn,n) ≥ n + 5, let us assume that χpg(Bn,n) < n + 5 say n + 4. We define proper vertex Communications on Applied Nonlinear Analysis ISSN: 1074-133X Vol 31 No. 6s (2024) https://internationalpubls.com 267 coloring of Bn,n is ꞷ(u1) = c1, ꞷ(ui) =ci, ꞷ( vi)=ci Ɐ 2 ≤ i ≤ n+1 and ꞷ( v1)= cn+4. Since v1 is adjacent to vi Ɐ 2 ≤ i ≤ n+1 for each edge vivj GCD ꞷ(v1, vi) ≠ 1. Thus, χpg(Bn,n) ≥ n + 5. Therefore, χpg(Bn,n)= n+ 5 when n ≡ 0 mod 6. Figure 6 Analytical Evaluation of the 𝐵5,5 4. Conclusion This paper demonstrates that several graph classes admits prime graceful coloring. Prime graceful coloring offer a unique structure where vertex colors are relatively prime and induce a proper edge coloring which potentially leads to application in areas yet to be explored. Further research can investigate prime graceful coloring in more complex graph families and explore their potential uses in areas where efficient and unique coloring schemes are crucial. References [1] English, S.; and Zhang, P.: On graceful colorings of trees, Mathematica Bohemica, vol.142, pp. 57-73, (2017). [2] Gallian, J.A.: A Dynamic Survey of Graph Labeling, The Electronic Journal of Combinatorics,18, (2015). [3] Murugarajan, P.; Aruldoss, R.: Prime Coloring Of Some Graphs, International Journal of Scientific & Technology Research, Volume 8, Issue 08, August (2019). [4] Nandhini, S.P.; Pooja Lakshmi, B.: Study on Prime Graceful Labeling for Some Special Graphs, NVEO, 1316113171, (2021). [5] Rosa, A.: On certain valuations of the vertices of a graph, Theory of graphs, (International)Symposium, Rome, July 1966), Gordon and Breach, N.Y. and Dunod Paris, 355, (1967). [6] Sayan Panma.; and Penying Rochanakul.: Prime-Graceful Graphs, Thai Journal of Mathematics, volume 19 number 4, (2021). [7] Selvarajan, T.M.; Subramoniam, R.: Prime Graceful Labeling, IJET, 750-752, (2018). [8] Siti Khoirunnisa.; Dafik.; Arika Indah Kristiana.; Ridho Alfarisi.; Graceful Coloring of Wheel Graph Family, International Journal of Academic and Applied Research, Vol. 5 Issue 4, Pages: 68-78, (2021). [9] Tout, A.; Dabboucy, A.N.; and Howalla, K.: Prime Labeling of Graphs, National AcademyScience Letters, Vol. 11, pp. 365-368, (1982). [10] Vernold Vivin, J.; Kowsalya, V.; Vimal Kumar, S.: On Star Chromatic Number of Prism Graph Families, TWMS.J.App.Eng.Math., 9, 687-692, (2019). [11] Zhenming Bi.; Alexis Byers.; Sean English.; Elliot Laforge.; Ping Zhang.; Graceful colorings of graph, The journal of combinatorial mathematics and combinatorial computing, Volume – 101, Pages - 101-119, (2017).