Bilangan Kromatik Permainan Graf Ubur-Ubur, Graf Siput, dan Graf Gurita

M Luthfi Abdurahman, Helmi Helmi, Fransiskus Fran


Graph coloring is the process of assigning colors to the vertices or edges of a graph. Specifically, coloring the vertices in graph coloring can be implemented in graph coloring games. This article aims to determine the game chromatic number of the jellyfish graph Jm,n, snail graph SIn, and octopus graph On. For example, give G as a simple, connected, and undirected graph and give two players, namely A as the first player and B as the secondary player. The two players A and B color all the vertices of graph G with available colors. The game’s rules are that A must ensure that all vertices of graph G are colored, while B aims to prevent graph G from being uncolored. Players A and B take turns coloring the vertices of graph G, ensuring that the color of neighboring vertices must be different, with A taking the first turn. If all vertices have been colored, A wins the game, but A loses if some vertices remain uncolored despite available colors, A loses. The smallest value of k for which A has a winning strategy in the game with k colors is the game chromatic number, denoted as χg(G). This thesis discusses the graph coloring game of the tadpole graph Tm,n, broom graph Bn,d, jellyfish graph Jm,n, and tribune graph Tn to find the game chromatic number. The results show that player A uses a strategy to color the vertex with the highest degree in the graph, ensuring that player A always wins. Therefore, the game chromatic number of the jellyfish graph, snail graph, and octopus graph is χg (Jm,n) = 3 for m, n ≥ 1, and χg (SIn) = 3 for n ≥ 1, while χg (On) = 3 for n = 2, 3, 4; χg (On) = 4 for n ≥ 5.


Jellyfish Graph; Snail Graph; Octopus Graph; Chromatic Numbers; Graph Coloring Games

Full Text:



N. Deo, Graph Theory with Applications to Engineering and Computer Science, Courier Dover Publications, 2017.

R. Munir, Matematika Diskrit, Edisi 3, Bandung: Informatika Bandung, 2010.

R. F. Sari, F. Rakhmawati, and N. Lela, “Implementasi Pewarnaan Graf Menggunakan Metode Algoritma Tabu Search Pada Penjadwalan Kerja Perawat,” G-Tech: Jurnal Teknologi Terapan, vol. 7, no. 1, 298-304, 2023, doi: 10.33379/gtech.v7i1.2021.

P. Pasnur, “Implementasi Algoritma Welch-Powell dalam Pembuatan Jadwal Ujian Akhir Semester,” Inspiration: Jurnal Teknologi Informasi dan Komunikasi, vol. 2, no. 1, 35-44, 2012, doi: 10.355585/inspir.v2i1.16.

R. J. Wilson, Introduction to Graph Theory Fourth Edition, England: Addison Wesley Longman Limited, 1996.

H. L. Bodlaender, “On The Complexity of Some Coloring Games,” International Journal of Foundations of Computer Science., vol. 2, no. 2, pp. 133-147, 1991, doi: 10.1142/S0129054191000091.

A. Mujib, “Bilangan Kromatik Permainan Graf Pot Bunga (CmSn) dan Graf Pohon Palem (CkPlSm),” TEOREMA: Teori Dan Riset Matematika, vol. 4, no. 1, pp. 13-22, 2019, doi: 10.25157/teorema.v4i1.1903.

M. S. Akhtar, U. Ali, Abbas G, and M. Batool, “On The Game Chromatic Number of Splitting Graphs of Path and Cycle,” Theoretical Computer Science, vol. 795, pp. 50-56, 2019, doi: 10.1016/j.tcs.2019.05.035.

T. Bartnicki, et al., “Game Chromatic Number of Cartesian Product Graphs,” The Electronic Journal Of Combinatorics, vol. 15, 2008,doi: 10.37236/796.

B. Gustiani, F. Fran, and N. M. Huda, “Pelabelan k-Prima pada Graf UburUbur,” Buletin Ilmiah Matematika, Statistika, dan Ilmu Terapan (Bimaster), vol. 13, no. 1, pp. 35-42, 2023, doi: 10.26418/bbimst.v13n1.74049.

I. I. Makhfudloh, Dafik, and R. Adawiyah, “Rainbow Connection pada Graf Siput, Graf Tunas Kelapa dan Graf Lotus,” CGANT Journal of Mathematics and Applications, vol. 4, no. 1, pp. 8-16, 2023, doi: 10.25037/cgantjma.v4i1.91.

I. I. Retnoningsih, Dafik, and S. Hussen, “Pewarnaan Titik pada Keluarga Graf Sentripetal,” CGANT Journal of Mathematics and Applications, vol. 3, no. 1, 2022, doi:

S. Rahayuningsih, Teori Graph dan Penerapannya, Jawa Timur:Universitas Wisnuwardhana Press Malang (Unidha Press), 2018.

J. M. Harris, J. L. Hirst, and M. J. Mossinghoff, Combinatorics and Graph Theory, New York: Springer, 2008, doi: 10.1007/978-0-387-79711-3.

J. A. Bondy and U. S. R. Murty, Graph Theory with Applications (Vol. 290), London: Macmillan, 1976.

R. Balakrishnan and K. Ranganathan, A Textbook of Graph Theory, Second Edition. Germany: Springer Science & Business Media, 2012, doi: 10.1007/978-1-4614-4529-6

K. Akbar and K. A. Sugeng, “Pelabelan Graceful pada Graf Siput dan Graf Ubur-Ubur,” in Pattimura Proceeding: Conference of Science and Technology, 2021, pp. 143-148, doi: 10.30598/pattimurasci.2021.knmxx.143-148.

H. Komarulloh, “Nilai Minimum Span pada Graf Gurita, Graf Siput, dan Graf Ubur-Ubur,” in Prosiding Galuk Mathematics National Conference, 2023, pp. 56-62.

A. E. Samuel and S. Kalaivani, “Prime Labelling For Some Octopus Related Graphs,” IOSR Journal of Mathematics (IOSR-JM), vol. 12, 2016, doi: 10.9790/5728-1206035764.


Copyright (c) 2024 M Luthfi Abdurahman, Helmi, Fransiskus

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

Jambura Journal of Mathematics has been indexed by

>>>More Indexing<<<

Creative Commons License

Jambura Journal of Mathematics (e-ISSN: 2656-1344) by Department of Mathematics Universitas Negeri Gorontalo is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License. Powered by Public Knowledge Project OJS. 

Editorial Office

Department of Mathematics, Faculty of Mathematics and Natural Science, Universitas Negeri Gorontalo
Jl. Prof. Dr. Ing. B. J. Habibie, Moutong, Tilongkabila, Kabupaten Bone Bolango, Gorontalo, Indonesia