A Study on Chromatic Number of Sierpinski’s Cycle Graph with Order n

Abstract

Graph coloring is a major area in Discrete Mathematics because it helps solve real-world problems like setting up network connections or assigning wireless radio frequencies. This dissertation focuses on finding the exact vertex chromatic number, which we write as ?(G), for a special class of recursive networks called Sierpinski Cycle Graphs, or S(k, G). These graphs are built step-by-step using a repeating, fractal-like pattern based on a simple starting cycle graph G.The way these graphs are made is detailed through a step-by-step construction method. For example, to make a level-2 graph like S(2, C4), we take four separate copies of a level-1 graph S(1, C4) and link them together at specific corner points called extreme vertices. To figure out the coloring limits as the graphs grow larger, we used mathematical induction as our main tool to track how the points and lines change at each level (k).For the graphs built on a 4-cycle base, S(k, C4), the math shows that connecting the separate blocks together never creates an odd-cycle conflict. Because of this, the network always stays bipartite, meaning we only ever need exactly 2 colors. ? S(k,G)=2 For the graphs built on a 5-cycle base, S(k, C5), things change. Because a 5-cycle has an odd number of corners, you cannot color it with just 2 colors without touching parts clashing. This odd-cycle conflict carries over into every new level of the graph. The proofs show that we can cleanly solve this using exactly 3 colors. ? S(k,G)=3

Introduction

This text introduces graph theory, particularly graph coloring and Generalized Sierpi?ski Graphs, and investigates the chromatic number of Sierpi?ski cycle graphs.

Graph theory studies mathematical structures consisting of vertices (nodes) and edges (connections). Introduced by Leonhard Euler through the Seven Bridges of Königsberg problem, graph theory has applications in numerous fields such as computer science, biology, sociology, economics, and communication networks.

A graph coloring is the assignment of colors to vertices such that no two adjacent vertices share the same color. The minimum number of colors required for a proper coloring is called the chromatic number, denoted by χ(G).

The text focuses on Generalized Sierpi?ski Graphs, which are self-similar recursive structures derived from a base graph. Originally introduced by Klavžar and Milutinovi? (1997) for complete graphs and later generalized by Gravier, Kovše, and Aline (2011) to any graph, these graphs are constructed recursively by creating copies of smaller graphs and connecting them according to specific rules.

The methodology applies graph-coloring principles to Sierpi?ski cycle graphs generated from cycle graphs C4C_4C4? and C5C_5C5?:

• For Sierpi?ski graphs based on C4C_4C4? (an even cycle), the graphs remain bipartite, requiring only 2 colors. Therefore:
  • χ(S(1, C?)) = 2
  • χ(S(2, C?)) = 2
  • χ(S(3, C?)) = 2
• For Sierpi?ski graphs based on C5C_5C5? (an odd cycle), 3 colors are necessary:
  • χ(S(1, C?)) = 3
  • χ(S(2, C?)) = 3

The study demonstrates that the chromatic number of a Sierpi?ski cycle graph remains the same as that of its underlying cycle graph: 2 for even cycles and 3 for odd cycles, regardless of the recursive construction stage.

Conclusion

Chromatic Number for Even Base Graph S(k, C_4): When we use a 4-cycle graph (C_4) as the starting base, the mathematical proofs show that connecting the different blocks together during expansion never creates an odd-cycle conflict. Because of this, the graph always stays bipartite no matter how many layers (k) we add. Therefore, we only need exactly two colors to properly color its vertices: ?(S (k,C_4 ) )=2 where k = 1,2,3…,n Chromatic Number for Odd Base Graph S(k, C5): When the starting base graph is changed to a 5-cycle (C5), things become different. Because a 5-cycle has an odd number of vertices, it is impossible to use just two colors without adjacent corners clashing. This odd-cycle conflict carries over into every new level of the graph. The tables prove that we can cleanly solve this using exactly three colors: ?(S (k,C_4 ) )=3 where k = 1,2,3…,n.

References

[1] Bondy J.A. and Murty U. S. R. [1976] “Graph theory with applications”, http://www.zib.de/groestschel/teaching/WS1314/BondyMurtyGTWA.pdf [2] Janka R.,RomanS.[2008] “Vertex distinguishing proper edge coloring of some regular graphs” Discrete mathematics, Vol.308, pp.795-802. [3] BapatR. B. [2010] “Graph and Matrices”, Springer-Verlag, New York. [4] Bing Z. [2013]“Multiple circular coloring as a model for scheduling”, Discrete Mathematics, Vol.3, pp.162-166. [5] Ling X. and JiangliangW.[2013]“Edge coloring of planer graphs without 6 cycles with two chords”, Open journal of Discrete Mathematics,Vol.(3), pp.83-85. [6] Geetha J., Somasundaram K.[2015] “Total coloring of generalized Sierpinski graphs”, Australasian Journal of Combinatorics, Vol. 63, Issue (1), pp. 58-69. [7] Akyar H. [2017] “On the incidence Chromatic Number of Sierpinski Graph”, IOSR Journal of Mathematics, Vol. 13, Issue (6), pp.72-79. [8] Bresar B., Ferme J. [2018] “Pacing colouring of Sierpinski-type graphs”, AequationesMathematicae, Vol. 92, Issue 6, pp.1091-1118. [9] Belmonte R., James M. and Singh B. (2024) \"Odd Chromatic Number of Graph Classes\", Mathematical Review and Analysis, Vol. (22), Issue (04), pp. 112-125. [10] Kumar A. (2023) “Graph coloring for Crop Sowing Optimization”, Int. J. Agriworld, vol. (04), Issue (02), pp. 7-9. [11] Kumar A., James H., and Singh B. (2019) “Chromatic number and chromatic index of product of two isomorphic regular graphs”, International of Advanced Scientific Research and Management. [12] Kumar A. (2017) “A study on Euler Graph and it’s application”, International Journal of Mathematics Trends and Technology, Vol. (43) [13] Domeshajouh,H.R.,[2018] “A topological lower bound for the chromatic number of a special family of graph”, Discrete Mathematics, Vol.341, pp. 508-512. [14] Kikyo H., Nakaura K. and Tsuboi A. (2026) \"On Chromatic Number of Countable Graphs\", Modeling and Analysis of Information Systems, Vol. (13), Issue (06), pp. 78-89. [15] Wilson R.J. and Watkins J.J. (2024) \"Historical Perspectives on the Four Color Theorem\", Modeling and Analysis of Systems, Vol. (09), Issue (08), pp. 17-30

Copyright

Copyright © 2026 Amit Mishra, Ashish Kumar, Chinta Mani Tiwari. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.