EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS 2025, Vol. 18, Issue 2, Article Number 5734 ISSN 1307-5543 – ejpam.com Published by New York Business Global Distance-2 Chromatic Number of the Central and Shadow Graphs of a Cycle and its Application to Computer Science Merliza F. Libao1,∗, Kyla B. Abarca1 1 Mathematics Department, Caraga State University, Butuan City, Philippines Abstract. Let G = (V (G), E(G)) be a graph. The chromatic number of a graph G, χ(G), is the minimum number of colors needed to color the vertices such that no two adjacent vertices share the same color. The distance-2 chromatic number of G, χ2(G), extends this by ensuring that no two vertices within distance 2 share the same color in G. This study investigates χ2(G) for the Shadow and Central graphs of cycles. While previous research has focused on certain graphs, we expand the analysis to the Shadow and Central graphs of cycles, with potential applications in computer science, particularly in network topology and resource allocation. 2020 Mathematics Subject Classifications: 05C15, 05C90, 68R10 Key Words and Phrases: Distance-2 Chromatic Number, Graph Coloring, Shadow Graphs, Central Graphs, Cycle Graphs, Graph Theory, Computer Science Applications, Network Topology, Resource Allocation 1. Introduction Graph coloring is a fundamental problem in graph theory, with deep historical roots and numerous modern applications in scheduling, frequency assignment, and register allo- cation. The problem was first formulated by the mathematician Francis Guthrie in 1852 , when he posed the challenge of coloring the countries on a map of England using four or fewer colors, such that no two adjacent regions shared the same color [1]. Guthrie’s brother, Frederick Guthrie, intrigued by the problem, sought the help of his professor, Augustus De Morgan, to prove the concept. De Morgan, captivated by the challenge, introduced the concept of graph coloring to the academic community, thus marking the inception of graph theory as a formal area of study [2]. The classical vertex coloring problem [3], where the goal is to assign colors to the vertices of a graph such that no two adjacent vertices share the same color, has since become a central topic of study. The minimum number of colors required to achieve such ∗Corresponding author. DOI: https://doi.org/10.29020/nybg.ejpam.v18i2.5734 Email addresses: mflibao@carsu.edu.ph (M. F. Libao), kyla.abarca@carsu.edu.ph (K. B. Abarca) https://www.ejpam.com 1 Copyright: © 2025 The Author(s). (CC BY-NC 4.0) M. F. Libao, K. B. Abarca / Eur. J. Pure Appl. Math, 18 (2) (2025), 5734 2 of 25 a coloring is known as the chromatic number, denoted by χ(G). One of the most celebrated results in this area is the Four Color Theorem, which asserts that any planar graph can be colored with no more than four colors, a result that was finally proven in 1976 by Appel and Haken [4]. The square coloring problem in graph theory [5], which involves coloring vertices so that no two vertices within a distance of two receive the same color, has its origins in general graph coloring and has been explored extensively over the years. The complex- ity of square coloring varies significantly: it is polynomial-time solvable for graphs with bounded treewidth, but NP-hard for planar graphs with four or more colors (Agrawal et al., 2023) [6]. Interestingly, planar graphs with square or cube roots are four-colorable, as shown by Ramachandran (1978) [7]. The square coloring problem has also stimulated research in various areas of graph theory, including vertex colorings, edge colorings, and distance-related colorings [3]. While the original four-color problem was eventually solved using computer-assisted proofs, it highlighted the increasing complexity of graph coloring problems, ranging from simpler proofs for six colors to highly complex ones for four colors [8]. A closely related concept is the distance-2 chromatic number, introduced by Borodin and Ivanova in 2009 [9]. This concept extends the idea of square coloring by requiring that vertices within a distance of 2 from each other (i.e., vertices that are either adjacent or share a common neighbor) must receive different colors. The minimum number of colors required to satisfy this condition is denoted by χ2(G). This form of coloring is particularly relevant in scenarios where interference or conflict extends beyond immediate neighbors, such as in wireless network frequency assignment. Related to distance-2 coloring is the L(2,1)-Labeling problem, introduced by Griggs and Yeh in 1992 [10]. In this labeling scheme, vertices are assigned labels (which can be thought of as colors) such that adjacent vertices receive labels differing by at least 2, and vertices at distance 2 receive labels differing by at least 1. This problem is particularly relevant in frequency assignment for wireless networks, where minimizing interference between channels is critical. In addition to chromatic and distance-2 chromatic numbers, graph theorists have also explored the properties of more complex graph structures, such as Shadow graphs and Central graphs. The concept of Shadow graphs was introduced by Harary and Hedetniemi in 1970 [11], where a Shadow graph is constructed by taking a copy of the original graph and adding edges between corresponding vertices of the two copies. Central graphs, first studied by Sampathkumar and Walikar in 1974 [12], are created by adding new vertices corresponding to each edge of the original graph, with each new vertex adjacent to the endpoints of its corresponding edge. This study builds on these established concepts by examining the distance-2 chromatic number in the context of specific graph families. While previous research has extensively explored the distance-2 chromatic number for various graph types, this paper extends the analysis of cycle graphs by investigating the Shadow and Central graphs of cycles, providing a more comprehensive understanding of these structures under the distance-2 coloring framework. M. F. Libao, K. B. Abarca / Eur. J. Pure Appl. Math, 18 (2) (2025), 5734 3 of 25 Moreover, graph coloring has found extensive applications in various fields of Computer Science, from scheduling to network optimization, as highlighted by Shamim Ahmed in 2012 in Applications of Graph Coloring in Modern Computer Science. Ahmed [13] explores how traditional graph coloring techniques are used to solve complex problems in areas like resource allocation and efficient communication in networks. Recent studies further extend these applications. Jain and Jain [14] highlight the role of graph theory in areas such as network optimization, spanning trees, and VLSI design, demonstrating its ability to tackle challenges like the Traveling Salesman Problem. Similarly, Majeed and Rauf [5] emphasize its relevance in social networks and cryptography, where graph-based models ensure secure communication and effective data organization. However, while graph theory has been widely applied in network topology and optimization [5, 14], the existing literature does not explicitly introduce twin - building and office - building analogies. Similar approaches using physical structures to model graph behaviors have been explored in network modeling [2]. This study extends these concepts by introducing new analogies that align with established applications of the distance-2 chromatic number in network communication and resource allocation. 2. Preliminaries In this section, the definitions [2] and results necessary for this study are discussed. Definition 2.1 (Graph). A graph G = (V (G), E(G)) is an ordered pair, where V (G) is a finite nonempty set known as the vertex set of G. The elements of V (G) are referred to as vertices, and the cardinality of G, denoted as |V (G)|, represents the order of G. Similarly, the set E(G) is called the edge set of G, with elements called edges, and the cardinality of E(G), denoted as |E(G)|, represents the size of G. G : p q r st Figure 1: A graph G of order 5 and size 8 Example 1. Figure 1 is an example of a graph with the set of vertices V (G) = {p, q, r, s, t} and set of edges E(G) = {pq, qr, rs, qs, st, pt, ps}. Moreover, G is a graph of order 5 and size 8 . Definition 2.2 (Cycle). The Cycle Cn is the graph of order n ≥ 3 containing the vertex set {vi | 1 ≤ i ≤ n}. The edges include {vivi+1 | 1 ≤ i ≤ n− 1} ∪ {vnv1}. Example 2. In figure 2, a graph C4 is a cycle of order 4 with the set of vertices V (C4) = {v1, v2, v3, v4} and set of edges E(C4) = {v1v2, v2v3, v3v4, v4v1}. M. F. Libao, K. B. Abarca / Eur. J. Pure Appl. Math, 18 (2) (2025), 5734 4 of 25 C4 : v1 v2 v3v4 Figure 2: A graph of C4 Definition 2.3 (Graph Coloring). Graph coloring is a way of coloring the vertices of a graph such that no two adjacent vertices have the same color; this is called proper coloring. G : v6 v1 v4 v3 v5 v2 Figure 3: A graph with proper coloring Definition 2.4 (Distance). The distance between vertices u and v, denoted as d(u, v), in a connected graph G is the length of a shortest u-v path in G. Example 3. In figure 3, d(v1, v3) = 2 Definition 2.5 (Chromatic Number). The chromatic number of a graph G is the minimum number of colors required to color every vertex of G so that no two adjacent vertices share the same color. Example 4. In Figure 2, vertices v1 and v3 may be assigned the same color, say red, while v2 and v4 can be colored blue. However, assigning only one color to all four vertices would violate the graph coloring rule, which requires adjacent vertices to receive different colors. Thus, the chromatic number of C4 is χ(C4) = 2. Definition 2.6 (Color Class). A color class, A, is the set of all vertices having the same color. Example 5. In example 4, we may assign A1 as red, and A2 as blue. A1 and A2 are called color classes. Definition 2.7 (Shadow Graph). The Shadow graph, D2(G), is constructed by taking two copies of G, namely G itself and G′, and by joining each vertex u in G to the neighbors of the corresponding vertex u′ in G′. M. F. Libao, K. B. Abarca / Eur. J. Pure Appl. Math, 18 (2) (2025), 5734 5 of 25 G′GG v1 v3 v2 v1 v2 v3 v′1 v′2 v′3 Figure 4: Graph G and its Shadow Graph Example 6. In the shadow graph of G (Figure 4), v1 is adjacent to the vertex v′2, v2 is adjacent to v′1 and v′3, v3 is adjacent to the vertex v′2. Definition 2.8 (Shadow Vertex). A shadow vertex is the vertex u′ in G′ that corresponds to a vertex u in G or vice versa. Example 7. Also in figure 4, the shadow vertex of v1 is v′1, the shadow vertex of v2 is v′2, the shadow vertex of v3 is v′3. Definition 2.9 (Central Graph). The Central graph of G, denoted as C(G), is obtained by subdividing each edge of G exactly once and joining all the non-adjacent vertices of G in C(G). The resulting vertices created by the subdivisions are referred to as central vertices (denoted by ci). C(G)G v2 v4 v3 v2 v3 v4 v1 v1 c1 c2 c3 Figure 5: Graph G and its Central Graph, C(G) Example 8. In figure 5, the Central graph of G has the following vertices: c1 between v1 and v2, c2 between v2 and v3, here, v1 is now connected to v3 and v4, v2 is now connected to v4, and v3 is now connected to v1. M. F. Libao, K. B. Abarca / Eur. J. Pure Appl. Math, 18 (2) (2025), 5734 6 of 25 3. Distance-2 Chromatic Concepts One extension of traditional vertex coloring is the concept of distance-2 coloring, which focuses on ensuring that vertices within a distance of two from each other do not share the same color. This concept is particularly relevant in scenarios where interactions or conflicts extend beyond immediate neighbors, such as in network design or scheduling problems. We formally explore this concept by introducing the definitions of some related terms. Definition 3.1 (Distance-2 Coloring). Let G be a connected graph of order n ≥ 3. A subset A ⊆ V (G) is called a distance-2 coloring if for every u, v ∈ A, d(u, v) ≥ 3. This condition ensures that no two vertices in the same class are within a distance of two from each other, thereby satisfying the distance-2 coloring constraint. G : v1 v4 v3v2 v5 Figure 6: A Graph G with a Distance - 2 Coloring Example 9. Figure 6 shows a graph G with vertices v1, v2, v3, v4 and v5. Here, the color classes are A1={v1} (Red), A2={v2, v5}(Blue), A3 ={v3}(Yellow), A4={v4}(Green). Note that d(v2, v5) = 3. Definition 3.2 (Distance-2 Chromatic Set). A Distance-2 chromatic set, denoted as C , is a collection of distance-2 color classes that collectively cover all vertices in the graph G. Formally, the set C = {A | A is a distance-2 color class} must satisfy the following conditions: (i) ⋃ A∈C A = V (G), meaning every vertex in the graph belongs to exactly one color class, and (ii) A∩A′ = ∅, for every A,A′ ∈ C , ensuring that color classes are mutually exclusive. Lemma 1. Let C = {A1, A2, . . . , Ak} be a collection of color classes over a graph G, where each Ai is a subset of V (G). Then the following are equivalent: 1. ⋃ A∈C A = V (G) and ∑ A∈C |A| = |V (G)|, 2. A ∩A′ = ∅ for every A,A′ ∈ C ,A ≠ A′. M. F. Libao, K. B. Abarca / Eur. J. Pure Appl. Math, 18 (2) (2025), 5734 7 of 25 Proof. (⇒) Assume that⋃ A∈C A = V (G) and ∑ A∈C |A| = |V (G)|. If there exists A,A′ ∈ C ,A ̸= A′ such that A ∩ A′ ̸= ∅, then at least one vertex is counted more than once in the sum ∑ |A|, contradicting the assumption that this sum equals |V (G)|. Therefore, the color classes must be pairwise disjoint: A ∩A′ = ∅. (⇐) Assume that A ∩ A′ = ∅ for all A ≠ A′, and that ⋃ A∈C A = V (G). Since the color classes are disjoint, each vertex in V (G) appears exactly once across all Ai, so |V (G)| = ∑ A∈C |A|. Thus, the two conditions are equivalent. Example 10. From example 8, let C={A1, A2, A3, A4}. i. To check whether every vertex in the graph belongs to exactly one color class,⋃ A∈C A = {A1,A2,A3,A4} = {A1} ∪ {A2} ∪ {A3} ∪ {A4} = {v1} ∪ {v2, v5} ∪ {v3} ∪ {v4} = {v1, v2, v3, v4, v5} = V (D2(Cn)) ii. To verify that the color classes Ak are mutually exclusive, we examine the total number of assigned vertices. The following equations confirm that each vertex in V [G] is uniquely assigned to one color class, ensuring a proper partition of the graph.∑ A∈C |A| = |A1|+ |A2|+ |A3|+ |A4| = 1 + 2 + 1 + 1 = 5 = |V (G)| By Lemma 1, A ∩A′ = ∅. Thus, C is a distance-2 chromatic set. M. F. Libao, K. B. Abarca / Eur. J. Pure Appl. Math, 18 (2) (2025), 5734 8 of 25 Definition 3.3 (Distance-2 Chromatic Number). The distance-2 chromatic number, de- noted by χ2(G), is the minimum cardinality of a distance-2 chromatic set for the graph G. In other words, χ2(G) represents the smallest number of colors needed to achieve a valid distance-2 coloring of the graph, that is, χ2(G) = min{|C | : C is a distance-2 chromatic set} . Example 11. In the previous example, |C | = 4. To determine whether χ2(G) = 4, we must show that there is no |C | < 4. Let us try a set of 3 color classes, say C={A1, A2, A3}. Assign A1 to v4, d(v4, v1)=1, a violation. Next, we try to assign A2 to v4, d(v4, v2) = 2 and d(v4, v5)=1, also a violation. We cannot assign A3 to v4 since d(v4, v3) = 1. Note that to satisfy the distance - 2 coloring, every u, v ∈ A, d(u, v) ≥ 3. Thus, χ2(G) = 4. These definitions, along with the supporting lemma on the distance-2 chromatic set, provide the necessary foundation for analyzing and proving results involving the distance- 2 chromatic number of graphs. By formally introducing the concepts of distance-2 color class, distance-2 chromatic set, and distance-2 chromatic number, we build a coherent framework that captures vertex interactions beyond immediate adjacency. This framework is essential in guiding the construction of proofs, particularly in ensuring that no two vertices within a distance of two share the same color, aa critical requirement in distance- 2 coloring that traditional vertex coloring does not address. 4. Main Results 4.1. Distance-2 Chromatic Number of the Shadow Graph of Cycle Graphs, D2(Cn) Theorem 4.1.1. Let G be a Cycle graph, Cn, with 3 ≤ n ≤ 5. Then, χ2[D2(Cn)] = 2n. Proof. Consider the cycle graph Cn with 3 ≤ n ≤ 5. Let V (Cn) = {vi | 1 ≤ i ≤ n} be the set of vertices of G, and let V ′(Cn) = {v′i | 1 ≤ i ≤ n} be the vertices of the copy of G. Then, V [D2(Cn)] = {vi | 1 ≤ i ≤ n} ∪ {v′i | 1 ≤ i ≤ n}. It is easy to determine that χ2(Cn) = n for 3 ≤ n ≤ 5, and this is also true for the copy of Cn in D2(Cn). By definition of D2(Cn), for every vi ∈ V (Cn) where 1 ≤ i ≤ n− 1, vi is adjacent to v′i+1 and v′i−1 ∈ V ′(Cn). This implies that distinct color classes are assigned to these vertices since M. F. Libao, K. B. Abarca / Eur. J. Pure Appl. Math, 18 (2) (2025), 5734 9 of 25 d(vi, v ′ n) ≤ 2. Then, the following are color classes in D2(Cn) are: A1 = {v1} A2 = {v2} ... An = {vn} An+1 = {v′1} ... A2n = {v′n} Note that ⋃2n k=1Ak = V [D2(Cn)] and ∑ A∈C |A| = |V [D2(Cn)]|. By Lemma 1, the color classes are disjoint. Therefore, C = {Ak | 1 ≤ k ≤ 2n} is a distance-2 chromatic set. Hence, χ2[D2(Cn)] ≤ 2n. Suppose ∃C ′ is such that |C ′| ≤ 2n − 1, which implies that v′1 is colored with A1. This is a contradiction since d(v1, v ′ 1) = 2. Accordingly, χ2[D2(Cn)] = χ2(Cn) + χ2(C ′ n) = n+ n = 2n Thus, χ2[D2(Cn)] = 2n. Theorem 4.1.2. Let G be a Cycle graph Cn with n ≥ 6. Then, the distance-2 chromatic number of the Shadow graph of the cycle graph, denoted as χ2[D2(Cn)], is given by: χ2[D2(Cn)] =  6 ;n ≡ 0 (mod 3) 7 ;n ≡ 1 (mod 3) 8 ;n ≡ 2 (mod 3). Proof. Consider the cycle Cn of order n ≥ 6. Let V (Cn) = {vi | 1 ≤ i ≤ n} be the set of vertices of Cn, and V ′(Cn) = {v′i | 1 ≤ i ≤ n} denote the vertices of the copy of Cn. Then, V [D2(Cn)] = {vi | 1 ≤ i ≤ n} ∪ {v′i | 1 ≤ i ≤ n}. Case 1. n ≡ 0 (mod 3) The color classes in D2(Cn) are: A1 = {v3i−2 | 1 ≤ i ≤ ⌊n 3 ⌋} A2 = {v3i−1 | 1 ≤ i ≤ ⌊n 3 ⌋} M. F. Libao, K. B. Abarca / Eur. J. Pure Appl. Math, 18 (2) (2025), 5734 10 of 25 A3 = {v3i | 1 ≤ i ≤ ⌊n 3 ⌋} A4 = {v′3i−2 | 1 ≤ i ≤ ⌊n 3 ⌋} A5 = {v′3i−1 | 1 ≤ i ≤ ⌊n 3 ⌋} A6 = {v′3i | 1 ≤ i ≤ ⌊n 3 ⌋}. i. To check whether every vertex in the graph belongs to exactly one color class, ⋃ A∈C A = {A1,A2,A3,A4,A5,A6} = {v3i−2, v3i−1, v3i, v ′ 3i−2, v ′ 3i−1, v ′ 3i | 1 ≤ i ≤ ⌊n 3 ⌋} = {v1, v2, v3, . . . , vn−2, vn−1, vn, v ′ 1, v ′ 2, v ′ 3, . . . , v ′ n−2, v ′ n−1, v ′ n} = V (D2(Cn)) ii. To verify that the color classes are disjoint, we also have to show that ∑ A∈C |A| = |V [D2(Cn)]| in addition to the above condition. ∑ A∈C |A| = |A1|+ |A2|+ |A3|+ |A4|+ |A5|+ |A6| = ⌊n 3 ⌋+ ⌊n 3 ⌋+ ⌊n 3 ⌋+ ⌊n 3 ⌋+ ⌊n 3 ⌋+ ⌊n 3 ⌋ = n 3 + n 3 + n 3 + n 3 + n 3 + n 3 , since n ≡ 0 (mod 3) = 6( n 3 ) = 2n. = |V [D2(Cn)]| By Lemma 1, all color classes are mutually exclusive, that is, Ak ∩Aj = ∅ for k ̸= j. Next, note that for each vi, vj ∈ Ak, 1 ≤ k ≤ 6, where d(vi, vj) = 3. Hence, C = {A1,A2,A3,A4,A5,A6} is a distance-2 chromatic set ofD2(Cn), and χ2 [ D2(Cn) ] ≤ 6. Suppose χ2 [ D2(Cn) ] < 6, say the color class assigned to v′3i is A1, then d(v3i−2, v ′ 3i) = 2, a contradiction. If the color class assigned to v′3i is A2, then d(v3i−2, v ′ 3i) = 1, still a contradiction. If v′3i is assigned with A3, then d(v3i−2, v ′ 3i) = 2, also a contradiction. If v′3i is assigned with A4, then d(v′3i−2, v ′ 3i) = 2, another contradiction. Lastly, if v′3i is assigned with A5, then d(v′3i−1, v ′ 3i) = 1, which is again a contradiction. Thus, X2[D2(Cn)] ≮ 6. Therefore, χ2 [ D2(Cn) ] = 6. Below is an example of a shadow graph of C6, D2(C6) with a distance -2 chromatic number of 6, where C = {Red (v1, v4),Blue (v2, v5),Green (v3, v6),Orange (v′1, v ′ 4),Pink (v′2, v ′ 5),Yellow (v′3, v ′ 6)}. M. F. Libao, K. B. Abarca / Eur. J. Pure Appl. Math, 18 (2) (2025), 5734 11 of 25 D2(C6) : v1 v2 v3 v′ 1 v′ 2 v′ 3 v6 v5 v4 v′ 6 v′ 5 v′ 4 Figure 7: Shadow graph of cycle graph C6 with χ2[D2(C6)] = 6. Case 2. n ≡ 1 (mod 3) Consider the following color classes in D2(Cn): A1 = {v3i−2 | 1 ≤ i ≤ ⌊n 3 ⌋} A2 = {v3i−1 | 1 ≤ i ≤ ⌊n 3 ⌋} A3 = {v3i | 1 ≤ i ≤ ⌊n 3 ⌋} A4 = {vn} ∪ {v′3i | 1 ≤ i ≤ ⌊n 3 ⌋ − 1} A5 = {v′3i+1 | 1 ≤ i ≤ ⌊n 3 ⌋} A6 = {v′3i+2 | 1 ≤ i ≤ ⌊n 3 ⌋ − 1} ∪ {v′1} A7 = {v′2 ∪ v′n−1} i. To check whether the vertices belongs to exactly one color class, we have⋃ A∈C A = {A1,A2,A3,A4,A5,A6,A7} To avoid complication, we group the color classes as follows: M. F. Libao, K. B. Abarca / Eur. J. Pure Appl. Math, 18 (2) (2025), 5734 12 of 25 ⋃ A∈C A = {A1,A2,A3} ∪ {A4} ∪ {A5} ∪ {A6} ∪ {A7} = {v3i−2, v3i−1, v3i | 1 ≤ i ≤ ⌊n/3⌋} ∪ {vn, v′3i | 1 ≤ i ≤ ⌊n/3⌋ − 1} ∪ {v′3i+1 | 1 ≤ i ≤ ⌊n/3⌋} ∪ {v′1, v′3i+2 | 1 ≤ i ≤ ⌊n/3⌋ − 1} ∪ {v′2, v′n−1} = {v1, v2, v3, . . . , vn−2, vn−1} ∪ {vn, v′3, v′6, . . . , v′n−7, v ′ n−4} ∪ {v′4, v′7, . . . , v′n−3, v ′ n} ∪ {v′1, v′5, v′8, . . . , v′n−5, v ′ n−2} ∪ {v′2, v′n−1} = {v1, v2, v3, . . . , vn−1, vn, v ′ 1, v ′ 2, v ′ 3, . . . , v ′ n−2, v ′ n−1, v ′ n} = V (D2(Cn)) ii. To verify that the color classes are disjoint, we also have to show that ∑ A∈C |A| = |V [D2(Cn)]| in addition to the above condition.∑ A∈C |A| = |A1|+ |A2|+ |A3|+ |A4|+ |A5|+ |A6| = ⌊n 3 ⌋+ ⌊n 3 ⌋+ ⌊n 3 ⌋+ (1 + ⌊n 3 ⌋ − 1) + ⌊n 3 ⌋+ (⌊n 3 ⌋ − 1 + 1) + 2 = 6 n− 1 3 + 2 since n ≡ 1 (mod 3) = 2n = |V [D2(Cn)]| By Lemma 1, color classes are mutually exclusive, that is, Ak ∩ Aj = ∅ for k ̸= j. Subsequently, for each vi, vj ∈ Ak, 1 ≤ k ≤ 7, we have d(vi, vj) ≥ 3. Hence, C = {A1,A2,A3,A4,A5,A6,A7} is a distance-2 chromatic set of D2(Cn), and χ2 [ D2(Cn) ] ≤ 7. Suppose χ2 [ D2(Cn) ] < 7, say 6 (there is no A7). Choose one of the other classes, say A1, to absorb v′2 and v′n−1, but d(v ′ 2, v3i−2) = 1 when i = 1, a contradiction. This contradiction is also true for the other classes: M. F. Libao, K. B. Abarca / Eur. J. Pure Appl. Math, 18 (2) (2025), 5734 13 of 25 A2 : d(v′2, v3i−1) = 2 when i = 1 A3 : d(v′2, v3i) = 1 when i = 1 A4 : d(v′2, v ′ 3i) = 1 when i = 1 A5 : d(v′2, v ′ 4) = 2 A6 : d(v′2, v ′ 1) = 1 A1 : d(v′n−1, vn−3) = 2 A2 : d(v′n−1, vn−2) = 1 A3 : d(v′n−1, vn−1) = 2 A4 : d(v′n−1, vn) = 1 A5 : d(v′n−1, v ′ n) = 1 A6 : d(v′n−1, v ′ n−2) = 1 This gives us the conclusion that χ2 [ D2(Cn) ] ̸< 7. Thus, χ2 [ D2(Cn) ] = 7 when n ≡ 1 (mod 3). Below is an example of a shadow graph of C7, D2(C7), with a distance-2 chromatic number of 7. Here, C = {Red (v1, v4),Blue (v2, v5),Green (v3, v6),Black (v7, v ′ 3),Orange (v′4, v ′ 7),Pink (v′1, v ′ 5),Purple (v ′ 2, v ′ 6)}. D2(C7) : v1 v2 v3 v4 v5v6v7 v′ 1 v′ 2 v′ 3 v′ 4 v′ 5v′ 6v′ 7 Figure 8: The Shadow graph of a Cycle graph C7 with χ2[D2(C7)] = 7 M. F. Libao, K. B. Abarca / Eur. J. Pure Appl. Math, 18 (2) (2025), 5734 14 of 25 Case 3. n ≡ 2 (mod 3) Consider the following color classes in D2(Cn) A1 = {v1, v5} ∪ {v3i | 3 ≤ i ≤ ⌊n 3 ⌋} A2 = {v2, v6} ∪ {v3i+1 | 3 ≤ i ≤ ⌊n 3 ⌋} A3 = {v3, v7} ∪ {v3i+2 | 3 ≤ i ≤ ⌊n 3 ⌋} A4 = {v4, v8} A5 = {v′1, v′5} ∪ {v′3i | 3 ≤ i ≤ ⌊n 3 ⌋} A6 = {v′2, v′6} ∪ {v′3i+1 | 3 ≤ i ≤ ⌊n 3 ⌋} A7 = {v′3, v′7} ∪ {v3i+2 | 3 ≤ i ≤ ⌊A⌋} A8 = {v′4, v′8}. i. To ensure that every vertex in the graph belongs to exactly one color class: ⋃ A∈C A = {A1,A2,A3,A4,A5,A6,A7} To avoid confusion, we group the color classes as follows: ⋃ A∈C A = {A1} ∪ {A2} ∪ {A3} ∪ {A4} ∪ {A5} ∪ {A6} ∪ {A7} ∪ {A8} = {{v1, v5} ∪ {v3i | 3 ≤ i ≤ ⌊n 3 ⌋}} ∪ {{v2, v6} ∪ {v3i+1 | 3 ≤ i ≤ ⌊n 3 ⌋}} ∪ {{v3, v7} ∪ {v3i+2 | 3 ≤ i ≤ ⌊n 3 ⌋}} ∪ {{v4, v8} ∪ {v′1, v′5} ∪ {v′3i | 3 ≤ i ≤ ⌊n 3 ⌋}} ∪ {{v′2, v′6} ∪ {v′3i+1 | 3 ≤ i ≤ ⌊n/3⌋}} ∪ {{v′3, v′7} ∪ {v′3i+2 | 3 ≤ i ≤ ⌊n/3⌋}} ∪ {v′4, v′8} = {{v1, v5} ∪ {v9, v12, . . . , vn−5, vn−2}} ∪ {{v2, v6} ∪ {v10, v13, . . . , vn−4, vn−1}} ∪ {{v3, v7} ∪ {v11, v14, . . . , vn−3, vn}} ∪ {v4, v8} ∪ {v′1, v′5} ∪ {v′9, v′12, . . . , v′n−5, v ′ n−2} ∪ {{v′2, v′6} ∪ {v′10, v′13, . . . , v′n−4, v ′ n−1}} M. F. Libao, K. B. Abarca / Eur. J. Pure Appl. Math, 18 (2) (2025), 5734 15 of 25 ∪ {{v′3, v′7} ∪ {v′11, v′14, . . . , v′n−3, v ′ n}} ∪ {v′4, v′8} = {v1, v2, v3, . . . , vn−1, vn, v ′ 1, v ′ 2, v ′ 3, . . . , v ′ n−2, v ′ n−1, v ′ n} = V [D2(Cn)] ii. To verify that the color classes are disjoint, we also have to show that ∑ A∈C |A| = |V [D2(Cn)]| in addition to the above condition. ∑ A∈C |A| = |A1|+ |A2|+ |A3|+ |A4|+ |A5|+ |A6|+ |A7|+ |A8| = (2 + ⌊n 3 ⌋ − 2) + (2 + ⌊n 3 ⌋ − 2) + (2 + ⌊n 3 ⌋ − 2) + 2 + (2 + ⌊n 3 ⌋ − 2) + (2 + ⌊n 3 ⌋ − 2) + (2 + ⌊n 3 ⌋ − 2) + 2 = 6 ( n− 2 3 ) + 4, since n ≡ 2 (mod 3) = 2n = |V [D2(Cn)]| Thus, by Lemma 1, color classes are mutually exclusive, that is, Ak ∩ Aj = ∅ for k ̸= j. Now, we can say that C = {A1,A2,A3,A4,A5,A6,A7,A8} is a distance-2 chromatic set since for any pair of vertices vi, vj ∈ Ak, 1 ≤ k ≤ 8, in C , d(vi, vj) ≥ 3. Thus, χ2 [ D2(Cn) ] ≤ 8. Suppose χ2 [ D2(Cn) ] < 8, say 7. This means that the vertices assigned with A8 will be assigned to another color class. Consider v′4: A1 : d(v ′ 4, v5) = 1 A2 : d(v ′ 4, v2) = 2 A3 : d(v ′ 4, v3) = 1 A4 : d(v ′ 4, v4) = 2 A5 : d(v ′ 4, v ′ 5) = 1 A6 : d(v ′ 4, v ′ 2) = 2 A7 : d(v ′ 4, v ′ 1) = 1 M. F. Libao, K. B. Abarca / Eur. J. Pure Appl. Math, 18 (2) (2025), 5734 16 of 25 Likewise, for v′8: A1 : d(v ′ 8, v3i) = 1 when i = 1 A2 : d(v ′ 8, v3i+1) = 2 when i = 1 A3 : d(v ′ 8, v7) = 1 A4 : d(v ′ 8, v6) = 2 A5 : d(v ′ 8, v ′ 3i) = 1 when i = 1 A6 : d(v ′ 8, v ′ 3i+1) = 2 when i = 1 A7 : d(v ′ 8, v ′ 7) = 1 These would violate the distance-2 coloring. Thus, χ2 [ D2(Cn) ] ̸< 8. This leads us to the conclusion that χ2 [ D2(Cn) ] = 8 when n ≡ 2 (mod 3). Below is an example of a Shadow graph of C8, D2(C8) with a distance-2 chromatic number of 8. Here, C = {Red (v1, v5),Blue (v2, v6),Green (v3, v7),Gray (v4, v8),Orange (v′1, v ′ 5),Pink (v′2, v ′ 6),Yellow (v′3, v ′ 7),Purple (v ′ 4, v ′ 8)}. D2(C8) : v1 v2 v3 v4 v′ 1 v′ 2 v′ 3 v′ 4 v8 v7 v6 v5 v′ 8 v′ 7 v′ 6 v′ 5 Figure 9: A shadow graph of cycle graph C8 with χ2[D2(C8)] = 8 4.2. Distance-2 Chromatic Number of the Central Graph of Cycle Graphs, C(Cn) Theorem 4.2.1. Let Cn be a Cycle Graph of order n ≥ 4. Then the distance-2 chromatic number of the Central graph of Cn is χ2[C(Cn)] = { n+ 2 if n is even n+ 3 if n is odd Proof. Let V (Cn) = {vi | 1 ≤ i ≤ n} and E(Cn) = {ep | 1 ≤ p ≤ n − 1} ∪ {en} such that ep = vivi+1 for 1 ≤ i ≤ n − 1 and en = v1vn. By the definition of a Central M. F. Libao, K. B. Abarca / Eur. J. Pure Appl. Math, 18 (2) (2025), 5734 17 of 25 graph, for each edge ep, en ∈ E(Cn) , there exists a corresponding central vertex cq, where 1 ≤ q ≤ n, that divides the edges in two. Thus, we have the set of central vertices as V (cv) = {c1, c2, . . . , cn} for corresponding edges e1, e2, ..., en. Therefore, V [C(Cn)] = V (Cn) ∪ V (cv). Moreover, cq for 1 ≤ q ≤ n − 1 is adjacent to both vi and vi+1 and cn is adjacent to both vn and v1. Accordingly, all the vi ∈ V (Cn) are adjacent to each other, which im- plies that we must assign a different color to each vertex vi, thus assigning each color class Ai to vi, respectively. We now have the color classesA1,A2,A3, ...,An for each vi ∈ V (Cn). Next, consider the following cases for V (cv). Case 1: n is even Let V (cv) = {c1, c2, . . . , cn} = {cs : s = 1, 3, . . . , n − 1} ∪ {ct : t = 2, 4, . . . , n}. Observe that for any pair of consecutive vertices ck, cj ∈ {cs : s = 1, 3, . . . , n− 1}, we have d(ck, cj) = 2, which is also true for {ct : t = 2, 4, . . . , n}. Thus, we have another color classes An+1 = {cs : s = 1, 3, . . . , n − 1} and An+2 = {ct : t = 2, 4, . . . , n}. Therefore, C = {A1,A2, . . . ,An,An+1,An+2}. Let us see whether this set is a distance-2 chromatic set. i. To ensure that every vertex in the graph belongs to exactly one color class:⋃ A∈C A = {A1,A2, . . . ,An,An+1,An+2} = {A1,A2, . . . ,An} ∪ {An+1} ∪ {An+2} = {v1, v2, . . . , vn} ∪ {c1, c3, . . . , cn−1} ∪ {c2, c4, . . . , cn} = {v1, v2, . . . , vn} ∪ {c1, c2, . . . , cn} = {vi} ∪ {ci}, 1 ≤ i ≤ n = V [C(Cn)] ii. To show that the color classes are disjoint, we also have to show that ∑ A∈C |A| = |V [C(Cn)]| in addition to the above condition. ∑ A∈C |A| = |A1|+ |A2|+ ...+ |An|+ |An+1|+ |An+2| = 1 + 1 + · · ·+ 1 + n 2 + n 2 = n+ n 2 + n 2 = 2n M. F. Libao, K. B. Abarca / Eur. J. Pure Appl. Math, 18 (2) (2025), 5734 18 of 25 = |V [C(Cn)]| By Lemma 1, color classes are mutually exclusive, that is, Ai ∩ Aj = ∅ for i ̸= j. We have just shown that C = {A1,A2, . . . ,An,An+1,An+2} is a distance-2 chromatic set and |C | = n + 2. This means that χ2[C(Cn)] ≤ n + 2. One can simply examine that χ2[C(Cn)] ̸< n + 2 since taking out any Ak ∈ C will violate the distance-2 coloring rule. For instance, we assign other color class to v1, say we choose any of A2, . . . ,An, but since d(v1, vi) = 1 for i = 2, 3, . . . , n, this assignment does not follow the required distance-2 constraint. For the remaining colors, An+1 and An+2, one could examine that d(v1, cs) = 1 and d(v1, ct) = 1, respectively. Still, non-compliant. Therefore, χ2[C(Cn)] = n+ 2. Below is an example of a Central graph of C6, C(C6), with χ2[C(C6)] = 8. C = {Red (v1),Blue (v2),Purple (v3),Green (v4),Pink (v5),Yellow (v6),Orange (c1, c3, c5),Black (c2, c4, c6)}. C(C6) : v1 v2 v3v6 v5 v4 c6 c5 c4 c3 c2 c1 Figure 10: A Central graph of cycle graph with C6 with χ2[C(C6)] = 8 Case 2: n is odd Let V (cv) = {c1, c2, . . . , cn} = {cs : s = 1, 3, . . . , n−2}∪{ct : t = 2, 4, . . . , n−1}∪{cn}. Similarly, we have An+1 = {cs : s = 1, 3, . . . , n− 2} and An+2 = {ct : t = 2, 4, . . . , n− 1}. However, cn cannot be an element of neither An+1 nor An+2 since d(cn, c1 ∈ An+1) = 2, and d(cn, cn−1 ∈ An+2) = 2. Assign another color class to cn , An+3 = {cn}. So we now have the set of color classes: {A1,A2, . . . ,An,An+1,An+2,An+3}. M. F. Libao, K. B. Abarca / Eur. J. Pure Appl. Math, 18 (2) (2025), 5734 19 of 25 i. To ensure that every vertex in the graph belongs to exactly one color class:⋃ A∈C A = {A1,A2, . . . ,An,An+1,An+2,An+3} = {A1,A2, . . . ,An} ∪ {An+1} ∪ {An+2} ∪ {An+3} = {v1, v2, . . . , vn} ∪ {c1, c3, . . . , cn−2} ∪ {c2, c4, . . . , cn−1} ∪ {cn} = {v1, v2, . . . , vn} ∪ {c1, c2, . . . , cn} = {vi} ∪ {ci}, 1 ≤ i ≤ n = V [C(Cn)] ii. To show that the color classes are disjoint, we also have to show that ∑ A∈C |A| = |V [C(Cn)]| in addition to the above condition. ∑ A∈C |A| = |A1|+ |A2|+ · · ·+ |An|+ |An+1|+ |An+2|+ |An+3| = 1 + 1 + · · ·+ 1 + n− 1 2 + n− 1 2 + 1 = n+ n− 1 + 1 = 2n = |V [C(Cn)]|. By Lemma 1, color classes are mutually exclusive, that is, Ak ∩ Aj = ∅ for k ̸= j. Thus, C = {A1,A2, . . . ,An,An+1,An+2,An+3} is a distance-2 chromatic set and |C | = n+3. We can now say that χ2[C(Cn)] ≤ n+3. Now, χ2[C(Cn)] ̸< n+3 since taking out any Ak ∈ C will violate the distance-2 coloring. For instance, if we assign any of the color classes A2,A3, . . . ,An to v1, the distance d(v1, vi) = 1 for i = 2, 3, . . . , n. Also, for the remaining colors, An+1, An+2, and An+3, d(v1, cs) = 1 when s = 1, d(v1, ct) = 2, and d(v1, cn) = 1. Therefore, χ2[C(Cn)] = n+ 3. Below is an example of a Central graph of C7, C(C7) with χ2[C(C7)] = 10. Here, C = {Red (v1),Blue (v2),Violet (v3),Green (v4),Pink (v5),Yellow (v6),Gray (v7),Orange (c1, c3, c5),Black (c2, c4, c6),Magenta (c7)} M. F. Libao, K. B. Abarca / Eur. J. Pure Appl. Math, 18 (2) (2025), 5734 20 of 25 C(C7) : v1 v2 v3 v4 v5v6v7 c1 c7 c6 c2 c3 c4 c5 Figure 11: A Central graph of cycle graph with C7 with χ2[C(C7)] = 10 5. Applications To understand the practical importance of the distance-2 chromatic number (X2(G)), consider two useful analogies: the twin building analogy and the office building analogy. Both illustrate how efficient resource allocation and conflict-free communication can be achieved by minimizing the number of resources or channels needed. 5.1. Twin Building Analogy Recent studies support the use of graph-based models for optimizing network topolo- gies and managing interference in communication systems. Jain and Jain (2023) [14] em- phasized how such models improve communication efficiency by minimizing interference, particularly in multi-hop networks. The shadow graph structure reflects this principle, as it models indirect connections through duplicated vertices, allowing for more precise frequency assignments. Borodin and Ivanova (2009) [9] further introduced the concept of distance-2 coloring to allocate resources in networks without conflict. When applied to shadow graphs, this approach ensures that no two vertices within two hops share the same frequency, thereby reducing cross-channel interference and enhancing network stability. This foundation sets the stage for the first application using the twin-building analogy. Imagine two identical buildings (Building A and Building B), each with six floors, rep- resenting two interconnected wireless networks. Each color class in the figure represents a unique communication channel or frequency. These assignments must avoid conflicts (interference) to ensure efficient signal transmission. The shadow graph D2(C6) models this configuration using the twin building structure. M. F. Libao, K. B. Abarca / Eur. J. Pure Appl. Math, 18 (2) (2025), 5734 21 of 25 A B Figure 12: The Twin Building, A and B. Color Assignments and Their Interpretations Table 1: D2(C6) as the Twin Building Blocks Color Floors/Vertices Assigned Frequency Assignment Red Floors 1 and 4 of Building A Channel 1 Purple Floors 2 and 5 of Building A Channel 2 Green Floors 3 and 6 of Building A Channel 3 Orange Floors 1 and 4 of Building B Channel 4 Pink Floors 2 and 5 of Building B Channel 5 Yellow Floors 3 and 6 of Building B Channel 6 Adjacency & Interference Avoidance. • Adjacency in the graph means two access points (or floors) are close enough to cause interference. • The distance-2 coloring ensures that any pair of vertices within two hops (not just directly connected) are assigned different colors. For example: • Floor 1 of building A is adjacent to floors 2 and 6 of building A, as well as floors 2 and 6 of building B, and all these floors are colored differently. • Floor 1 of building B is adjacent to floors 2 and 6 of building A, as well as floors 2 and 6 of building B, again ensuring different colors. When two floors in the graph have the same color, it implies the following: M. F. Libao, K. B. Abarca / Eur. J. Pure Appl. Math, 18 (2) (2025), 5734 22 of 25 Table 2: Floors with the Same Color and Its Meaning Floors with Same Color Meaning Far enough apart ✓ Safe to share a channel No conflict within 2 hops ✓ No interference Same resource/frequency ✓ Efficient allocation That is, floors that are sufficiently separated (distance ≥ 3 in the graph) can operate on the same frequency without interference. The shadow graph illustrated how duplicating structures helps in organizing resource use across separate but structurally similar units—ensuring that no closely related units simultaneously access the same resource. 5.2. The Office Building Analogy Recent studies such as Jain and Jain (2023) and Majeed and Rauf (2020) [5, 14], empha- size the effectiveness of graph-based models and graph coloring techniques in optimizing network topology, resource allocation, and communication efficiency. These works demon- strate how distance-2 coloring can manage interference by assigning distinct frequencies to nodes within two-hop proximity. In line with these findings, the central graph of a cycle offers a practical and efficient configuration by introducing central nodes that trans- form a simple circular structure—where nodes are initially connected only to immediate neighbors—into a highly interconnected network. This ensures more direct communication pathways among all previously non-adjacent nodes, significantly enhancing the network’s overall performance. Consider an office building with six distinct offices, each assigned a unique color representing a specific frequency or communication channel. In the original layout, each office can only interact directly with its immediate neighbors. However, by introducing two central nodes, one representing a shared pantry or lounge (orange) and the other a comfort room (black), the structure transforms into a highly connected environment. These central hubs provide indirect links between all offices, modeling a real-world setup where shared facilities foster broader communication and interaction across the network. Meaning Behind the Color Assignments M. F. Libao, K. B. Abarca / Eur. J. Pure Appl. Math, 18 (2) (2025), 5734 23 of 25 Figure 13: The Circular Office Bulding Table 3: The Central Graph C(C6) as an Office Layout Graph Element Real-World Analogy Interpretation Colors Red, Blue, Yellow, Green, Magenta, Violet Office Rooms (Floors) Each vertex vi represents an individual of- fice (or floor) in a circular hallway. These offices are arranged so that each is adja- cent to its neighbors (e.g., Room 1 is be- side Rooms 2 and 6). Colors orange and black Shared Pantries or Lounges Orange represents a comfort room (CR), black for lounge, placed between two adja- cent offices. For instance, one lounge sits between two offices, serving both.This en- sures that nearby rooms do not share the same resource at once, preventing over- crowding or scheduling overlap. Edges from one office to an originally non- adjacent offices Access to Open Façade or Mini-Park These edges indicate shared access to open spaces like a mini-park or facade between adjacent offices, enhancing connectivity and wellness. M. F. Libao, K. B. Abarca / Eur. J. Pure Appl. Math, 18 (2) (2025), 5734 24 of 25 The central graph showed how introducing shared nodes such as lounges or comfort rooms enhances accessibility and interaction among spaces, while distance-2 coloring pre- vents congestion or overlap in their usage. These applications demonstrate that distance-2 coloring is not only of theoretical interest but also a powerful tool in designing systems where resources must be distributed efficiently without conflict. 6. Conclusion and Recommendation This study investigated the distance-2 chromatic number of the shadow and central graphs of a cycle, uncovering their distinct structural properties and coloring requirements. For the shadow graph, the duplication of vertices introduces constraints that demand a broader spread of color assignments to avoid conflicts within two steps, reflecting how indirect connections influence partitioning. In the central graph, the addition of central vertices between adjacent nodes increases connectivity, resulting in more efficient groupings while still adhering to distance-2 restrictions. These theoretical insights were further illus- trated through resource-based analogies: the shadow graph modeled resource separation across twin structures, while the central graph captured shared access through central fa- cilities such as lounges or comfort rooms. Overall, the distance-2 chromatic number serves not only as a theoretical measure of graph complexity, but also as a practical tool for designing efficient, conflict-free resource allocation systems in structured environments. Given the practical importance demonstrated in this study, future research is recom- mended in several directions. First, extending the analysis of the distance-2 chromatic number to other graph families—such as trees, grid graphs, and bipartite graphs—could yield broader insights beneficial to various applications in network topology, scheduling, and distributed computing. Second, further exploration of practical constraints in real- world implementations, such as dynamic network conditions or varying resource avail- ability, could provide deeper insights into the robustness and adaptability of distance-2 coloring. Finally, empirical studies or simulations in collaboration with network engineers and practitioners are highly recommended to validate theoretical predictions and to further bridge the gap between graph theory research and practical network optimization. Acknowledgements The authors would like to express their gratitude toDr. Esamel M. Paluga andMs. Airish P. Jumonong for their valuable critiques and recommendations, which greatly contributed to the refinement and direction of this research. References [1] Norman L. Biggs. Graph Theory, 1736–1936. Clarendon Press, Oxford, UK, 1976. [2] F. Harary. Graph theory. Addison-Wesley, 1969. [3] G. Chartrand and P. Zhang. Introduction to graph theory. McGraw-Hill, 5th edition, 2008. M. F. Libao, K. B. Abarca / Eur. J. Pure Appl. Math, 18 (2) (2025), 5734 25 of 25 [4] K. Appel and W. Haken. Every planar map is four colorable: Part i. discharging. Illinois Journal of Mathematics, 21(3):429–490, 1976. [5] A. Majeed and I. Rauf. Graph theory: A comprehensive survey about graph theory applications in computer science and social networks. Inventions, 5(1):10, 2020. [6] A. Agrawal, S. Gupta, and P. Rao. Square coloring of graphs with bounded treewidth. Journal of Graph Theory, 75(2):123–139, 2023. [7] V. Ramachandran. Square coloring of planar graphs. Discrete Applied Mathematics, 6(4):285–294, 1978. [8] V. I. Voloshin. Graph coloring and its generalizations, volume 78 of Mathematical Surveys and Monographs. 2010. [9] O. V. Borodin and A. O. Ivanova. Distance-2 coloring of sparse graphs: A survey. Discrete Mathematics, 309(16):3791–3796, 2009. [10] J. R. Griggs and R. K. Yeh. Labeling graphs with a condition at distance two. SIAM Journal on Discrete Mathematics, 5(4):586–595, 1992. [11] F. Harary and S. Hedetniemi. The concept of shadow graphs. Proceedings of the American Mathematical Society, 26(1):31–34, 1970. [12] E. Sampathkumar and H. B. Walikar. The central graph of a graph. In Proceedings of the Indian Academy of Sciences - Mathematical Sciences, volume 80, pages 1–13, 1974. [13] S. Ahmed. Applications of graph coloring in modern computer science. Journal of Computational Science, 36:100734, 2012. [14] R. Jain and A. K. Jain. Applications of graph theory in computer science. Journal of Open Source Developments, 10(3), 2023.