## RESEARCH ARTICLE • OPEN ACCESS

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

## M. Luthfi Abdurahman, Helmi Helmi, dan Fransiskus Fran

## Volume 6, Issue 1, Pages 118–124, February 2024
Submit 5 Januari 2024, Direvisi 25 Februari 2024, Disetujui 27 Februari 2024 To Cite this Article : M. L. Abdurahman, H. Helmi, dan F. Fran,“Bilangan Kromatik Permainan Graf Ubur-Ubur, Graf Siput, dan Graf Gurita”, Jambura J. Math , vol. 6, no. 1, pp. 118–124, 2024, https://doi.org/10.37905/jjom.v6i1.23958
© 2024 by author(s)

## JOURNAL INFO • JAMBURA JOURNAL OF MATHEMATICS
u Homepage : http://ejurnal.ung.ac.id/index.php/jjom/index Ǽ Journal Abbreviation : Jambura J. Math. Х Frequency : Biannual (February and August) Ŷ Publication Language : English (preferable), Indonesia  DOI : https://doi.org/10.37905/jjom ʢ Online ISSN : 2656-1344 ǽ Editor-in-Chief : Hasan S. Panigoro Ÿ Publisher : Department of Mathematics, Universitas Negeri Gorontalo ƒ Country : Indonesia ̰ OAI Address : http://ejurnal.ung.ac.id/index.php/jjom/oai  Google Scholar ID : iWLjgaUAAAAJ Ͳ Email : info.jjom@ung.ac.id

## JAMBURA JOURNAL • FIND OUR OTHER JOURNALS
Jambura Journal of
Biomathematics Jambura Journal of Mathematics Education Jambura Journal of Probability and Statistics EULER : Jurnal Ilmiah Matematika, Sains, dan Teknologi

## Bilangan Kromatik Permainan Graf Ubur-Ubur, Graf Siput, dan Graf Gurita
M Luthfi Abdurahman 1 , ∗ , Helmi Helmi 1 , dan Fransiskus Fran 1
1 Jurusan Matematika, Fakultas MIPA, Universitas Tanjungpura, Indonesia
ABSTRAK. Pewarnaan graf adalah proses memberikan warna pada simpul atau sisi graf. Secara khusus, pewarnaan simpul graf dapat diimplementasikan dalam permainan pewarnaan graf. Artikel ini membahas tentang penentuan bilangan kromatik permainan graf ubur-ubur J m,n , graf siput SI n , dan graf gurita O n . Misalkan diberikan G graf sederhana, terhubung, dan tak berarah serta diberikan dua pemain yaitu A sebagai pemain pertama dan B sebagai pemain kedua. Dua pemain A dan B mewarnai setiap simpul pada graf G dengan warna yang disediakan. Aturan permainannya adalah A harus memastikan setiap simpul graf G telah diwarnai dan B mencegah A mewarnai se- tiap simpul graf G . Pemain A dan B saling bergiliran mewarnai setiap simpul graf G dengan warna yang berbeda pada simpul yang bertetangga. Jika setiap simpul diwarnai dengan warna yang tersedia, maka A memenangkan permainan dan A dinyatakan kalah jika ada simpul yang tidak dapat diwarnai. Nilai terkecil dari k ketika A meme- nangkan permainan dengan k warna disebut bilangan kromatik permainan yang disimbolkan dengan χ g ( G ) . Hasil yang diperoleh yaitu A menggunakan strategi mewarnai derajat terbesar suatu graf terlebih dahulu agar A selalu menang. Dengan demikian, bilangan kromatik permainan dari graf ubur-ubur, graf siput, dan graf gurita adalah χ g ( J m,n ) = 3 untuk m, n ≥ 1 , χ g ( SI n ) = 3 untuk n ≥ 1 , dan χ g ( O n ) = 3 untuk n = 2 , 3 , 4 ;
χ g ( O n ) = 4 untuk n ≥ 5 .
ABSTRACT. 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 J m,n , snail graph SI n , and octopus graph O n . 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 T m,n , broom graph B n,d , jellyfish graph J m,n , and tribune graph T n 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 ( J m,n ) = 3 for m, n ≥ 1 and χ g ( SI n ) = 3 for n ≥ 1 , while χ g ( O n ) = 3 for n = 2 , 3 , 4 ; χ g ( O n ) = 4 for n ≥ 5 .
This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution-NonComercial 4.0 International License. Editorial of JJBM: Department of Mathematics, Uni- versitas Negeri Gorontalo, Jln. Prof. Dr. Ing. B. J. Habibie, Bone Bolango 96554, Indonesia.

## 1. Pendahuluan
Teori graf merupakan bagian dari matematika diskrit yang dikenalkan oleh Leonhard Euler pada tahun 1736 untuk memec- ahkan permasalahan Jembatan Konigsberg [1] . Graf G didefin- isikan sebagai himpunan terurut ( V, E ) dengan notasi G = ( V, E ) . Simbol V adalah himpunan berhingga tak kosong dise- but simpul pada graf G dan E adalah himpunan berhingga dise- but sisi yang menghubungkan beberapa simpul pada graf G [2] . Dalam pengimplementasiannya, teori graf merepresentasikan ob- jek dengan simpul dan hubungan antar objek dengan sisi. Salah
∗ Penulis Korespondensi.
Check for updates
Research Article

## ARTICLE HISTORY
Submit 5 Januari 2024
Direvisi 25 Februari 2024 Disetujui 27 Februari 2024

## KATA KUNCI
Graf Ubur-ubur Graf Siput Graf Gurita Bilangan Kromatik Permainan Pewarnaan Graf

## KEYWORDS
Jellyfish Graph Snail Graph Octopus Graph Chromatic Numbers
Graph Coloring Games
satu topik graf adalah pewarnaan graf yang dapat digunakan un- tuk memecahkan permasalahan jadwal kerja perawat [3] dan jad- wal ujian akhir semester [4] .
Pewarnaan graf merupakan metode pemberian warna pada beberapa objek pada graf yang pertama kali dicetuskan oleh Fran- cis Guthrie tahun 1852 [1] . Pewarnaan graf terdiri dari pewar- naan simpul, sisi, maupun wilayah graf. Artikel ini membahas tentang pengembangan dari pewarnaan simpul graf. Pewarnaan pada graf G dapat dilakukan jika memilih satu dari k warna ke suatu simpul sehingga setiap simpul bertetangga memiliki warna yang berbeda [4] . Nilai minimal k warna yang dapat diberikan
Email : luthfialkhawarismi2@student.untan.ac.id. (M. L. Abdurahman) Homepage : http://ejurnal.ung.ac.id/index.php/jjom/index / E-ISSN : 2656-1344 © 2024 by the Author(s).
pada graf G disebut bilangan kromatik graf G dan dinotasikan dengan χ ( G ) = k [5] . Bilangan kromatik sangat diperlukan un- tuk membantu dalam menemukan hasil dari artikel ini.
Salah satu pengembangan dari pewarnaan graf adalah per- mainan pewarnaan graf. Konsep permainan pewarnaan graf di- gagas oleh Hans L. Boadlaender tahun 1991 [6] . Graf yang di- gunakan bersifat sederhana, yaitu graf yang tidak memiliki sisi ganda dan loop . Selain itu, syarat lainnya adalah harus menggu- nakan graf terhubung dan tidak berarah dengan jumlah pemain sebanyak dua orang. Penelitian sebelumnya telah membahas per- mainan pewarnaan graf. Penelitian tersebut di antaranya adalah penentuan bilangan kromatik permainan graf pot bunga dan po- hon palem yang diperkenalkan oleh Mujib [7] . Kemudian, terda- pat penelitian lain seperti bilangan kromatik permainan pemisa- han graf lintasan dan lingkaran oleh Akhtar et.al. [8] , dan bilangan kromatik permainan graf kartesian dari penelitian Bartnicki et.al.
[9] .
Beberapa penelitian terkait graf ubur-ubur, graf siput, maupun graf gurita banyak dilakukan sebelumnya. Penelitian yang dilakukan oleh Gustiani et.al. [10] menemukan bahwa graf ubur-ubur adalah graf k -prima saat melakukan pelabelan. Nilai rainbow connection graf siput sebesar lima ditemukan berdasarkan hasil penelitian Makhfudloh et.al. [11] . Penelitian dari Retnon- ingsih et.al. [12] berhasil menemukan bilangan kromatik graf gu- rita sebesar tiga. Permainan pewarnaan pada graf ubur-ubur, graf siput, dan graf gurita dapat dilakukan karena ketiga graf memi- liki sifat sederhana, terhubung, dan tidak berarah. Oleh karena itu, penelitian mengenai graf ubur-ubur, graf siput, dan graf gu- rita dapat dikembangkan dengan cara mencari bilangan kromatik permainan seperti yang ditunjukkan pada penelitian sebelumnya [7–9] . Diberikan dua pemain A dan B bermain pewarnaan simpul pada graf G dengan himpunan warna C = { c 1 , c 2 , c 3 , . . . , c k } . Pemain A berusaha agar setiap simpul terwarnai, sedangkan B harus mencegahnya. Ketika permainan dimulai, A menjadi pe- main pertama. Jika setiap simpul terwarnai, maka A menang dan jika sebaliknya, maka B menang. Nilai k terkecil agar A meme- nangkan permainan disebut bilangan kromatik permainan den- gan simbol χ g ( G ) [7] .
Penelitian tentang permainan pewarnaan graf juga telah di- lakukan sebelumnya seperti yang ditunjukkan pada [7–9] . Mu- jib [7] menemukan bahwa bilangan kromatik permainan graf pot bunga dan graf pohon palem masing-masing sebesar tiga. Se- mentara itu, Akhtar et.al. [8] menemukan bahwa terdapat peruba- han nilai bilangan kromatik permainan graf berdasarkan jumlah setiap simpul. Adapun Bartnicki et.al. [9] membahas tentang bi- langan kromatik permainan graf kartesian. Selain itu, referensi lain tentang teori graf dan terapannya yang turut dijadikan seba- gai pendukung dalam penyusunan artikel ini dapat dilihat pada [13–19] . Penelitian dari Akbar & Sugeng [17] menunjukkan bahwa graf siput dan graf gurita adalah graf graceful . Selanjutnya, telah ditunjukkan bahwa nilai minimum span dari graf ubur-ubur, graf siput, dan graf gurita berturut-turut adalah 2 n + 1 , n + 4 , dan m + n + 1 [18] . Penelitian lain yang dilakukan oleh Samuel & Kalaivani [19] menunjukkan bahwa graf gurita adalah graf prima.
Merujuk pada penelitian [7–9] , dilakukan penelitian lanju- tan mengenai bilangan kromatik permainan graf ubur-ubur, graf siput, dan graf gurita karena terdapat keunikan yang perlu dikem- bangkan dari ketiga graf tersebut. Pada penelitian ini, dilakukan
permainan pewarnaan graf ubur-ubur, graf siput, dan graf gu- rita. Penelitian ini sangat penting untuk dilakukan sebagai acuan dalam penelitian lebih lanjut. Lebih lanjut, proses pencarian bi- langan kromatik permainan pada penelitian ini, menggunakan strategi dari para pemainnya ditambah dengan keunikan dari masing-masing graf. Dengan demikian, artikel ini ditulis den- gan tujuan untuk menentukan bilangan kromatik permainan graf ubur-ubur, graf siput, dan graf gurita.

## 2. Metode
Penelitian ini menggunakan metode studi literatur seba- gai dasar dalam membangun landasan teori graf dan diteruskan dengan teori mencari bilangan kromatik permainan melalui per- mainan pewarnaan graf yang bersumber dari beberapa artikel, buku, ataupun referensi yang lain. Metode tersebut digunakan untuk menentukan bilangan kromatik permainan graf ubur-ubur, graf siput, dan graf gurita.
Adapun tahapan penelitian dalam menentukan bilangan kromatik permainan adalah:
1. Melakukan kajian teoritis untuk mengetahui definisi bilan- gan kromatik permaian dengan teorema yang mendukung.
2. Memberikan contoh permainan pewarnaan graf sebagai gambaran dalam penentuan bilangan kromatik permainan.
3. Menjelaskan definisi graf ubur-ubur, graf siput, dan graf gu- rita.
4. Membentuk teorema bilangan kromatik permainan graf ubur-ubur, graf siput, dan graf gurita.
5. Membuktikan teorema tersebut menggunakan pembuktian secara matematis.
Sebelum menentukan bilangan kromatik permainan, ter- lebih dahulu diberikan contoh suatu graf, beberapa teorema yang menjadi landasan dalam menentukan bilangan kromatik permainan, dan contoh permainan pewarnaan graf.
Contoh 1. [13] Diberikan graf G dengan himpunan simpul V ( G ) = { v 1 , v 2 , v 3 , v 4 } dan himpunan sisi E ( G ) = { e 1 , e 2 , e 3 , e 4 } . Banyaknya simpul dan sisi graf G berturut- turut dinotasikan dengan | V ( G ) | dan | E ( G ) | , seperti diilus- trasikan pada Gambar 1 . Berdasarkan ilustrasi pada Gambar 1 , maka | V ( G ) | = 4 dan | E ( G ) | = 4 .
Gambar 1. Graf G
Selanjutnya, diberikan beberapa teorema tentang per- mainan pewarnaan graf.
Teorema 1. [7] Diberikan G sebuah graf dan ∆ ( G ) merupakan derajat terbesarnya, maka χ ( G ) ≤ χ g ( G ) ≤ ∆ ( G ) + 1 .
Bukti . Misalkan G graf dengan himpunan simpul V ( G ) dan him- punan sisi E ( G ) : (i) Simpul pada graf G tidak dapat diwarnai dengan warna se- banyak k apabila jumlah warna yang tersedia kurang dari χ ( G ) . Hal tersebut menyebabkan bilangan kromatik per- mainan lebih dari χ ( G ) sehingga χ g ( G ) ≥ χ ( G ) . (ii) Diasumsikan A dapat mewarnai setiap simpul v i ∈ V ( G ) dengan warna simpul tetangga v i berbeda, maka A akan se- lalu menang. Hal tersebut terjadi saat warna yang tersedia berjumlah ∆ ( G ) + 1 sehingga χ g ( G ) ≤ ∆ ( G ) + 1 . Berdasarkan poin (i) dan (ii), maka χ ( G ) ≤ χ g ( G ) ≤ ∆ ( G ) + 1 .
Teorema 2. [7] Diberikan graf lintasan P n dengan n simpul dan n − 1 sisi, maka bilangan kromatik permainan graf lintasan adalah χ g ( P n ) = 2 untuk n = 2 , 3 dan χ g ( P n ) = 3 untuk n ≥ 4 .
Bukti . Akan dibuktikan bahwa χ g ( P n ) = 2 untuk n = 2 , 3 dan χ g ( P n ) = 3 untuk n ≥ 4 . Misalkan P n graf lintasan dengan himpunan simpul V ( P n ) dan sisi E ( P n ) . Ditunjukkan bahwa χ ( P n ) = 2 untuk n = 2, 3. Hasil χ ( P n ) = 2 muncul akibat pewarnaan pada simpul graf P 2 dan P 3 . Diberikan him- punan warna C = { c 1 , c 2 } . Graf P 2 dapat diwarnai oleh dua warna yang berbeda. Sedangkan simpul berderajat terbesar P 3 diwarnai dengan c 1 , sehingga simpul lainnya diwarnai dengan c 2 . Dengan demikian, χ ( P 2 ) = χ ( P 3 ) = 2. Untuk n ≥ 4, dike- tahui bahwa χ ( P n ) = 2 dengan ∆ ( P n ) = 2 . Berdasarkan Teo- rema 1 , maka interval bilangan kromatik permainan graf lintasan adalah 2 ≤ χ g ( P n ) ≤ 3 . Asumsikan pemain A mewarnai simpul berderajat dua, misalkan v i diwarnai dengan c 1 , maka pemain B memberikan warna c 2 pada v i +2 . Akibatnya, sim- pul v i +1 tidak dapat diwarnai dengan warna. Dengan demikian, χ g ( P n ) ≥ 3 sehingga 3 ≤ χ g ( P n ) ≤ 3 atau χ g ( P n ) = 3 .
Teorema 1 dan 2 , selanjutnya digunakan untuk membuk- tikan teorema tentang bilangan kromatik permainan. Lebih khusus, Teorema 1 digunakan untuk menentukan batas bawah dan batas atas bilangan kromatik permainan, sedangkan Teorema 2 digunakan untuk mencari bilangan kromatik permainan. Selain itu, Teorema 2 digunakan untuk melakukan permainan pewar- naan graf seperti yang ditujukan pada Contoh 2 .
Contoh 2. Diberikan hasil permainan pewarnaan graf G dari Gambar 1 melalui ilustrasi pada Gambar 2 . Diberikan him- punan warna C = { merah, hijau, kuning } , maka A da- pat memulai permainan. Misalkan A mewarnai v 2 dengan c 1 , maka B mewarnai simpul lain seperti v 4 dengan c 2 . Sim- pul v 1 dan v 3 tidak dapat diwarnai dengan c 1 dan c 2 se- hingga simpul tersebut harus diberikan warna lain. Misalkan A mewarnai v 1 dengan c 3 dan B mewarnai v 3 dengan c 2 . Dengan demikian, pemain A memenangkan permainan.
Gambar 2. Permainan pewarnaan graf G

## 3. Hasil dan Pembahasan
Pada bagian ini, ditunjukkan nilai dari bilangan kromatik permainan graf ubur-ubur, graf siput, dan graf gurita.

## 3.1. Bilangan Kromatik Permainan Graf Ubur-Ubur
Sebelum menentukan bilangan kromatik permainan graf ubur-ubur, terlebih dahulu dijelaskan mengenai definisi graf ubur-ubur, bilangan kromatik graf ubur-ubur, dan derajat terbe- sar graf ubur-ubur.
Definisi 1. [17] Graf ubur-ubur J m,n adalah graf yang terbentuk dari himpunan simpul
V ( J m,n ) = { v i | 1 ≤ i ≤ 2 m + n + 2 }
dan himpunan sisi
E ( J m,n ) = { v i v 2 m + n +1 | 1 ≤ i ≤ n } ∪ { v i v 2 m + n +2 | 1 ≤ i ≤ n } ∪ { v n + i v 2 m + n +1 | 1 ≤ i ≤ m } ∪ { v m + n + i v 2 m + n +2 | 1 ≤ i ≤ n } ∪ { v 2 m + n +1 v 2 m + n +2 } .
Ilustrasi graf ubur-ubur J m,n dapat dilihat pada Gambar 3 dengan | V ( J m,n ) | = 2 m + n + 2 dan | E ( J m,n ) | = 2 m + 2 n + 1 .
Gambar 3. Graf ubur-ubur J m,n
Mengacu pada Definisi 1 dan Gambar 3 , dapat ditunjukkan bahwa derajat terbesar graf ubur-ubur adalah ∆ ( J m,n ) = m + n + 1 sebagai batas atas Teorema 1 . Kemudian, dirumuskan teo- rema yang menjelaskan tentang bilangan kromatik graf ubur-ubur sebagai batas bawah Teorema 1 . Pencarian bilangan kromatik
graf ubur-ubur dapat dilakukan dengan menggunakan Algoritma Welch-Powell [4] . Bilangan kromatik graf ubur-ubur dapat dilihat pada Teorema 3 .
Teorema 3. Diberikan graf ubur-ubur dengan 2 m + n + 2 simpul dan 2 m + 2 n + 1 sisi, maka χ ( J m,n ) = 3 untuk m, n ≥ 1 .
Bukti . Akan dibuktikan bahwa χ ( J m,n ) = 3 untuk m, n ≥ 1 . Berdasarkan Algoritma Welch-Powell, dilakukan pewarnaan sim- pul graf ubur-ubur. Pertama, salah satu simpul yang memiliki de- rajat terbesar diwarnai dengan warna pertama. Kemudian, di- lakukan pewarnaan terhadap simpul-simpul lain. Namun, karena terdapat tiga simpul yang saling bertetangga satu sama lain, maka pewarnaan dapat dilakukan dengan tiga warna. Dengan demikian, χ ( J m,n ) = 3 .
Secara formal, rumusan teorema bilangan kromatik per- mainan graf ubur-ubur dinyatakan pada Teorema 4 .
Teorema 4. Diberikan graf ubur-ubur dengan 2 m + n + 2 simpul dan 2 m + 2 n + 1 sisi, maka χ g ( J m,n ) = 3 untuk m, n ≥ 1 .
Bukti . Akan dibuktikan bahwa χ g ( J m,n ) = 3 untuk m, n ≥ 1 . Berdasarkan Teorema 1 , maka nilai bilangan kromatik permainan graf ubur-ubur adalah 3 ≤ χ g ( J m,n ) ≤ m + n + 2 dengan χ g ( J m,n ) bilangan asli. Bilangan kromatik permainan diten- tukan berdasarkan metode pada Teorema 2 . Diberikan himpunan warna C = { c 1 , c 2 , c 3 } . Pemain A mewarnai terlebih dahulu simpul v 2 m + n +1 atau v 2 m + n +2 sebagai simpul berderajat terbe- sar. Permainan pewarnaan graf diawali dengan A mewarnai sim- pul v 2 m + n +1 dengan c 1 . (i) Apabila B mewarnai v 2 m + n +2 dengan c 2 , karena d ( v i ) = 2 , i = 1 , 2 , . . . , n , maka v i tidak dapat diwarnai dengan c 1 atau c 2 sehingga harus diwarnai dengan c 3 . Kemudian, para pemain saling bergiliran dalam mewarnai. Karena v j , j = n + 1 , . . . , m + n, m + n + 1 , . . . , 2 m + n saling bebas, maka sisa simpul lainnya dapat diwarnai dengan tiga warna. (ii) Apabila B mewarnai simpul selain v 2 m + n +2 tanpa mengu- rangi unsur generalisasi semisal v n dengan c 2 , maka A dapat mewarnai simpul lain. Jika A mewarnai v 2 m + n +2 dengan c 3 , maka B dapat mewarnai v i dengan c 2 atau v j dengan warna yang berbeda berdasarkan v 2 m + n +1 dan v 2 m + n +2 . Berdasarkan poin (i), maka sisa simpul graf dapat diwarnai dengan tiga warna.
Berdasarkan poin (i) dan (ii), maka A selalu memenangkan per- mainan sehingga χ g ( J m,n ) ≤ 3 . Dengan demikian, maka 3 ≤ χ g ( J m,n ) ≤ 3 atau χ g ( J m,n ) = 3 .
Contoh implementasi Teorema 4 dapat diilustrasikan pada Contoh 3 .
Contoh 3. Diberikan graf ubur-ubur J 4 , 3 yang diilustrasikan pada Gambar 4 , dimana pemain A dan B memulai per- mainan pewarnaan graf tersebut. Diberikan himpunan warna C = { merah, hijau, biru } . Pemain A mewar- nai v 12 dengan warna merah. Kemudian, pemain B mewar-
nai v 13 dengan warna hijau. Setelah itu, pemain A mewar- nai v 1 dengan warna biru. Pemain B mewarnai v 4 den- gan warna hijau. Selanjutnya, pemain A mewarnai v 8 den- gan warna merah. Berdasarkan Teorema 2, maka v 2 dan v 3 hanya dapat diwarnai dengan warna biru. Simpul lainnya yaitu v 4 hingga v 11 diwarnai dengan warna yang berbeda berdasarkan v 12 dan v 13 . Pemain A dan B saling bergiliran dalam permainan hingga semua simpul terwarnai. Dengan demikian, χ g ( J 4 , 3 ) = 3 dan A memenangkan permainan.
Gambar 4. Permainan pewarnaan graf ubur-ubur J 4 , 3

## 3.2. Bilangan Kromatik Permainan Graf Siput
Sebelum menentukan bilangan kromatik permainan graf siput, terlebih dahulu dijelaskan mengenai definisi graf siput.
Definisi 2. [18] Graf siput SI n adalah graf yang terbentuk dari himpunan simpul
V ( SI n ) = { v i | 1 ≤ i ≤ n + 6 }
dan himpunan sisi
E ( SI n ) = { v i v n +3 | 1 ≤ i ≤ n } ∪ { v i v n +4 | 1 ≤ i ≤ n } ∪ { v n +2 v n +4 , v n +3 v n +4 , v n +2 v n +5 , v n +3 v n +5 , v n +1 v n +2 , v n +6 v n +2 } .
Ilustrasi graf siput SI n dapat dilihat pada Gambar 5 dengan | V ( SI n ) | = n + 6 dan | E ( SI n ) | = 2 n + 6 .
Mengacu pada Definisi 2 dan Gambar 5 , dapat ditunjukkan bahwa derajat terbesar graf siput adalah ∆ ( SI n ) = n + 2 seba- gai batas atas Teorema 1 . Kemudian, dirumuskan teorema yang menjelaskan tentang bilangan kromatik graf siput sebagai batas bawah Teorema 1 . Pencarian bilangan kromatik graf ubur-ubur dapat dilakukan dengan menggunakan Algoritma Welch-Powell [4] . Bilangan kromatik graf siput dapat dilihat pada Teorema 5 .
Teorema 5. Diberikan graf siput dengan n +6 simpul dan 2 n +6 sisi, maka χ ( SI n ) = 3 untuk n ≥ 1 .
Bukti . Akan dibuktikan bahwa χ ( SI n ) = 3 untuk n ≥ 1 . Berdasarkan Algoritma Welch-Powell, dilakukan pewarnaan sim- pul graf siput. Pertama, salah satu simpul yang memiliki derajat terbesar diwarnai dengan warna pertama. Kemudian, dilakukan pewarnaan terhadap simpul-simpul lain. Namun, karena terda- pat tiga simpul yang saling bertetangga satu sama lain, maka pe- warnaan dapat dilakukan dengan tiga warna. Dengan demikian, χ ( SI n ) = 3 .
Secara formal, rumusan teorema bilangan kromatik per- mainan graf siput dinyatakan pada Teorema 6 .
Teorema 6. Diberikan graf siput dengan n +6 simpul dan 2 n +6 sisi, maka χ g ( SI n ) = 3 untuk n ≥ 1 .
Bukti . Akan dibuktikan bahwa χ g ( SI n ) = 3 . Berdasarkan Teo- rema 1 , maka nilai bilangan kromatik permainan graf siput adalah 3 ≤ χ g ( SI n ) ≤ n + 3 dengan χ g ( SI n ) bilangan asli. Bilangan kromatik permainan ditentukan berdasarkan metode pada Teo- rema 2 . Diberikan himpunan warna C = { c 1 , c 2 , c 3 } . Pemain A mewarnai terlebih dahulu simpul v n +3 atau v n +4 sebagai simpul berderajat terbesar. Permainan pewarnaan graf diawali dengan A mewarnai simpul v n +3 dengan c 1 . (i) Apabila B mewarnai v n +4 dengan c 2 , karena d ( v i ) = 2 , i = 1 , 2 , . . . , n , maka v i tidak dapat diwarnai dengan c 1 atau c 2 sehingga harus diwarnai dengan c 3 . Kemudian, para pe- main saling bergiliran dalam mewarnai. Permainan terus di- lakukan sehingga simpul yang tersisa dapat diwarnai dengan tiga warna.
(ii) Apabila B mewarnai simpul selain v n +4 tanpa mengurangi unsur generalisasi semisal v n +2 dengan c 2 , maka A dapat mewarnai simpul lain. Jika A mewarnai v n +1 dengan c 1 , maka B dapat mewarnai v i , i = 1 , 2 , . . . , n dengan c 2 . Berdasarkan poin (i), maka sisa simpul pada graf dapat di- warnai dengan tiga warna.
Berdasarkan poin (i) dan (ii), maka A selalu memenangkan per- mainan sehingga χ g ( SI n ) ≤ 3 . Dengan demikian, 3 ≤ χ g ( SI n ) ≤ 3 atau χ g ( SI n ) = 3 .
Contoh implementasi Teorema 6 dapat diilustrasikan pada Contoh 4 .
Contoh 4. Diberikan graf ubur-ubur SI 3 yang diilustrasikan pada Gambar 6 , dimana pemain A dan B memulai per- mainan pewarnaan graf tersebut. Diberikan himpunan
warna C = { merah, hijau, biru } . Pemain A mewarnai v 6 dengan warna merah. Kemudian, pemain B mewarnai v 1 dengan warna hijau. Setelah itu, pemain A mewarnai v 8 dengan warna hijau. Pemain B mewarnai v 5 dengan warna merah. Selanjutnya, A mewarnai v 4 dengan warna hijau. Berdasarkan Teorema 2 , maka v 7 hanya dapat diwarnai den- gan warna biru. Pemain A dan B saling bergiliran dalam per- mainan hingga semua simpul terwarnai. Dengan demikian, χ g ( SI 3 ) = 3 dan A memenangkan permainan.
Gambar 6. Permainan pewarnaan graf siput SI 3

## 3.3. Bilangan Kromatik Permainan Graf Gurita
Sebelum menentukan bilangan kromatik permainan graf gurita, terlebih dahulu dijelaskan mengenai definisi graf gurita.
Definisi 3. [19] Graf gurita O n adalah graf hasil kombinasi an- tara graf kipas dan graf bintang yang terbentuk dari himpunan simpul dengan
V ( O n ) = { u i | i = 1 , 2 , . . . , 2 n + 1 }
dan himpunan sisi
E ( O n ) = { u 1 u i | 1 ≤ i ≤ 2 n + 1 } ∪ { u i u i +1 | 2 ≤ i ≤ n } .
Ilustrasi graf gurita O n dapat dilihat pada Gambar 7 dengan | V ( O n ) | = 2 n + 1 dan | E ( O n ) | = 3 n − 1 .
Gambar 7. Graf gurita O n
Mengacu pada Definisi 3 dan Gambar 7 , dapat ditunjukkan bahwa derajat terbesar graf gurita adalah ∆ ( O n ) = 2 n seba- gai batas atas Teorema 1 . Selanjutnya, dirumuskan teorema yang
menjelaskan tentang bilangan kromatik graf siput sebagai batas bawah Teorema 1 . Pencarian bilangan kromatik graf ubur-ubur dapat dilakukan dengan menggunakan Algoritma Welch-Powell [4] . Bilangan kromatik graf siput dapat dilihat pada Teorema 7 .
Teorema 7. Diberikan graf siput dengan 2 n +1 simpul dan 3 n − 1 sisi, maka χ ( O n ) = 3 untuk n ≥ 1 .
Bukti . Akan dibuktikan bahwa χ ( O n ) = 3 untuk n ≥ 1 . Berdasarkan Algoritma Welch-Powell, dilakukan pewarnaan sim- pul graf siput. Pertama, salah satu simpul yang memiliki derajat terbesar diwarnai dengan warna pertama. Kemudian, dilakukan pewarnaan terhadap simpul-simpul lain. Namun, karena terda- pat tiga simpul yang saling bertetangga satu sama lain, maka pe- warnaan dapat dilakukan dengan tiga warna. Dengan demikian, χ ( O n ) = 3 .
Secara formal, rumusan teorema bilangan kromatik per- mainan graf gurita dinyatakan pada Teorema 8 .
Teorema 8. Diberikan graf gurita O n dengan 2 n + 1 simpul, maka nilai dari χ g ( O n ) adalah
χ g ( O n ) = { 3 , untuk n = 2 , 3 , 4 4 , untuk n ≥ 5 .
Bukti . Akan dibuktikan bahwa
χ g ( O n ) = { 3 , untuk n = 2 , 3 , 4 4 , untuk n ≥ 5 .
Berdasarkan Teorema 1 , diketahui nilai bilangan kromatik per- mainan graf gurita adalah 3 ≤ χ g ( O n ) ≤ 2 n + 1 dengan χ g ( O n ) bilangan asli. Bilangan kromatik permainan ditentukan berdasarkan metode pada Teorema 2 . Diberikan himpunan warna C = { c 1 , c 2 , c 3 , c 4 } . Pemain A mewarnai terlebih dahulu sim- pul berderajat terbesar.
Untuk n = 2 , 3 , 4 , diberikan graf gurita O 4 . Permainan pewarnaan graf diawali dengan A mewarnai simpul u 1 dengan c 1 . (i) Apabila B mewarnai u 5 dengan c 2 , maka u 4 tidak dapat di- warnai dengan c 1 atau c 2 sehingga harus diwarnai dengan c 3 . Kemudian, A mewarnai u 4 dengan c 3 . Para pemain saling bergiliran dalam mewarnai. Karena simpul u j , j = 6 , . . . , 11 saling bebas, maka sisa simpul lainnya dapat di- warnai dengan tiga warna.
(ii) Apabila B mewarnai simpul selain u 5 semisal u 3 dengan c 2 , maka A dapat mewarnai simpul u 5 dengan c 2 . Jika A mewar- nai u 5 dengan c 2 , maka B dapat mewarnai u 4 dengan c 3 . Berdasarkan poin (i), maka sisa simpul graf dapat diwarnai dengan tiga warna.
Berdasarkan poin (i) dan (ii), maka A selalu memenangkan permainan sehingga χ g ( O n ) ≤ 3 . Dengan demikian, 3 ≤ χ g ( O n ) ≤ 3 atau χ g ( O n ) = 3 dengan n = 2 , 3 , 4 . Untuk n ≥ 5 , diberikan graf gurita O n . Permainan pewar- naan graf diawali dengan A mewarnai simpul u 1 dengan c 1 .
(a) Apabila B mewarnai u n +1 dengan c 2 , maka u n tidak dapat diwarnai dengan c 1 atau c 2 sehingga harus diwarnai dengan c 3 . Kemudian, A mewarnai u n dengan c 3 . Selanjutnya, pe- main B mewarnai u n − 2 dengan c 3 . Akibatnya, simpul u n − 1 tidak dapat diwarnai dengan c 1 , c 2 , atau c 3 sehingga harus diwarnai dengan c 4 . Para pemain saling bergiliran dalam mewarnai. Karena simpul u j , j = n + 2 , . . . , 2 n + 1 sal- ing bebas, maka simpul yang tersisa dapat diwarnai dengan empat warna.
(b) Apabila B mewarnai simpul selain u n +1 tanpa mengurangi unsur generalisasi semisal u n dengan c 2 , maka A dapat mewarnai simpul u n +2 dengan c 2 . Ketika A mewarnai u n +2 dengan c 2 , pemain B mewarnai u n − 2 dengan c 3 . Akibat- nya, simpul u n − 1 harus diwarnai dengan c 4 . Berdasarkan poin (a), maka sisa simpul graf dapat diwarnai dengan em- pat warna.
Berdasarkan poin (a) dan (b), maka A selalu memenangkan permainan sehingga χ g ( O n ) ≤ 4 . Karena terdapat simpul u n − 1 yang harus diwarnai dengan c 4 , maka graf tersebut tidak dapat diwarnai dengan tiga warna. Akibatnya, χ g ( O n ) ≥ 4 . Dengan demikian, 4 ≤ χ g ( O n ) ≤ 4 atau χ g ( O n ) = 4 dengan n ≥ 5 .
Contoh implementasi Teorema 8 dapat diilustrasikan pada Contoh 5 .
Contoh 5. Diberikan graf gurita O 5 yang diilustrasikan pada Gambar 8 , dimana pemain A dan B memulai permainan pe- warnaan graf tersebut. Diberikan himpunan warna C = { merah, hijau, biru, kuning } . Pemain A mewarnai u 1 dengan warna merah. Kemudian, pemain B mewarnai u 6 dengan warna hijau. Setelah itu, A mewarnai u 4 dengan warna hijau. Pemain B mewarnai u 2 dengan warna biru. Se- lanjutnya, A mewarnai u 11 dengan warna hijau. Berdasarkan Teorema 2 , maka u 3 hanya dapat diwarnai dengan warna kuning. Pemain A dan B saling bergiliran dalam per- mainan hingga semua simpul terwarnai. Dengan demikian, χ g ( O 5 ) = 4 dan A memenangkan permainan.
Gambar 8. Permainan pewarnaan graf gurita 0 5

## 4. Kesimpulan
Jika χ ( G ) bilangan kromatik suatu graf dan ∆ ( G ) derajat terbesar suatu graf, maka nilai bilangan kromatik permainan graf ubur-ubur, graf siput, dan graf gurita adalah 3 ≤ χ g ( J m,n ) ≤ m + 2 n + 2 , 3 ≤ χ g ( SI n ) ≤ n + 3 , dan 3 ≤ χ g ( O n ) ≤ JJoM | Jambura J. Math
2 n + 1 . Dengan demikian, bilangan kromatik permainan dari graf ubur-ubur, graf siput, dan graf gurita adalah χ g ( J m,n ) = 3 untuk m, n ≥ 1 , χ g ( SI n ) = 3 untuk n ≥ 1 , dan χ g ( O n ) = 3 untuk n = 2 , 3 , 4 ; χ g ( O n ) = 4 untuk n ≥ 5 .
Kontribusi Penulis. M. Luthfi Abdurahman: Konseptualisasi, metodologi, studi literatur, visualisasi, dan penulisan naskah. Helmi: Konseptualisasi, metodologi, analisis formal, validasi, tin- jauan penulisan, dan supervisi. Fransiskus Fran: Konseptualisasi, metodologi, analisis formal, validasi, tinjauan penulisan, supervisi, dan pendanaan. Semua penulis telah membaca dan menyetujui versi manuskrip yang diterbitkan.
Ucapan Terima Kasih. Para penulis menyampaikan terima kasih kepada editor dan reviewer atas pembacaan yang cermat, kritik yang mendalam, dan rekomendasi yang praktis untuk meningkatkan kualitas tulisan ini.
Pembiayaan. Penelitian ini tidak menerima pembiayaan eksternal.
Konflik Kepentingan. Para penulis menyatakan tidak ada konflik ke- pentingan yang terkait dengan artikel ini.

## Referensi
[1] N. Deo, Graph Theory with Applications to Engineering and Computer Science, Courier Dover Publications, 2017.
[2] R. Munir, Matematika Diskrit , Edisi 3, Bandung: Informatika Bandung, 2010.
[3] R. F. Sari, F. Rakhmawati, and N. Lela, “Implementasi Pewarnaan Graf Menggunakan Metode Algoritma Tabu Search Pada Penjadwalan Kerja Per- awat,” G-Tech: Jurnal Teknologi Terapan , vol. 7, no. 1, 298-304, 2023, doi: 10.33379/gtech.v7i1.2021 .
[4] 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 .
[5] R. J. Wilson, Introduction to Graph Theory Fourth Edition, England: Addison Wesley Longman Limited, 1996.
[6] H. L. Bodlaender, “On The Complexity of Some Coloring Games,” Interna- tional Journal of Foundations of Computer Science., vol. 2, no. 2, pp. 133-147, 1991, doi: 10.1142/S0129054191000091 .
[7] A. Mujib, “Bilangan Kromatik Permainan Graf Pot Bunga ( C m S n ) dan Graf Pohon Palem ( C k P l S m ) ,” TEOREMA: Teori Dan Riset Matematika, vol. 4, no. 1, pp. 13-22, 2019, doi: 10.25157/teorema.v4i1.1903 .
[8] M. S. Akhtar, U. Ali, Abbas G, and M. Batool, “On The Game Chromatic Num- ber of Splitting Graphs of Path and Cycle,” Theoritical Computer Science , vol. 795, pp. 50-56, 2019, doi: 10.1016/j.tcs.2019.05.035 .
[9] T. Bartnicki, et al., “Game Chromatic Number of Cartesian Product Graphs,” The Electronic Journal Of Combinatorics, vol. 15, 2008,doi: 10.37236/796 .
[10] B. Gustiani, F. Fran, and N. M. Huda, “Pelabelan k -Prima pada Graf Ubur- Ubur,” Buletin Ilmiah Matematika, Statistika, dan Ilmu Terapan (Bimaster), vol. 13, no. 1, pp. 35-42, 2023, doi: 10.26418/bbimst.v13n1.74049 .
[11] 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 .
[12] 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: http://doi.org/10.25037/cgantjma.v3i1.75 .
[13] S. Rahayuningsih, Teori Graph dan Penerapannya , Jawa Timur:Universitas Wis- nuwardhana Press Malang (Unidha Press), 2018.
[14] 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 .
[15] J. A. Bondy and U. S. R. Murty, Graph Theory with Applications (Vol. 290), Lon- don: Macmillan, 1976.
[16] R. Balakrishnan and K. Ranganathan, A Textbook of Graph Theory, Second Edi- tion. Germany: Springer Science & Business Media, 2012, doi: 10.1007/978- 1-4614-4529-6
[17] 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 .
[18] H. Komarulloh, “Nilai Minimum Span pada Graf Gurita, Graf Siput, dan Graf Ubur-Ubur,” in Prosiding Galuk Mathematics National Conference, 2023, pp. 56- 62.
[19] A. E. Samuel and S. Kalaivani, “Prime Labelling For Some Octopus Re- lated Graphs,” IOSR Journal of Mathematics (IOSR-JM), vol. 12, 2016, doi: 10.9790/5728-1206035764 .