## KADIKMA: Jurnal Matematika dan Pendidikan Matematika
Vol. 14, No. 1, April 2023, Hal. 20-29 e-ISSN : 2686-3243 ; p-ISSN : 2085-0662 https://jurnal.unej.ac.id/index.php/kadikma https://doi.org/10.19184/kdma.v14i1.38551

## BILANGAN KROMATIK GRACEFUL PADA SUBDIVISI GRAF SIKLUS COMB GRAF STAR
Eko Waluyo 1* , Endah Tri Wisudaningsih 1 , Masruro 1 1 Universitas Islam Zainul Hasan Genggong, Indonesia *E-mail: mruro066@gmail.com
Article History: Received: 07-01-2023 ; Revised: 23-02-2023 ; Accepted: 27-03-2023

## ABSTRAK
Pewarnaan  graceful  merupakan  kombinasi  antara  konsep  graceful  dan  pewarnaan  simpul. Pewarnaan graceful didefinisikan sebagai pemberian label pada titik suatu graf G yang memenuhi fungsi injektif dari himpunan titik ke himpunan bilangan bulat tak negatif {1, 2, … , 𝑘} sedemikian hingga  setiap  sisi 𝑢𝑣 di  G    mendapat  label |𝑐(𝑢) − 𝑐(𝑣)| ,  maka  label  setiap  sisi  akan  berbeda. Penelitian  ini  bertujuan  untuk  mengetahui  pewarnaan  graceful  dan  bilangan  kromatik  pada  graf (𝐶 𝑛 ▷ 𝑆 𝑚 ) .  Penelitian  ini  merupakan  jenis  penelitian  eksploratif  dengan  menggunakan  metode deduktif aksiomatik dan metode pendeteksi pola. Penelitian ini menghasilkan satu teorema tentang pewarnaan  graceful  pada  graf  siklus  comb  graf  star  yang  terdiri  atas  tiga  kasus  yaitu 𝜒 𝑔 (𝐶 𝑛 ▷ 𝑆 𝑚 ) = 𝑚 + 6; untuk 𝑛 ≡ 1 𝑚𝑜𝑑 3 , 𝜒 𝑔 (𝐶 𝑛 ▷ 𝑆 𝑚 ) = 𝑚 + 6; untuk 𝑛 ≡ 2 𝑚𝑜𝑑 3 ,  dan 𝜒 𝑔 (𝐶 𝑛 ▷ 𝑆 𝑚 ) = 𝑚 + 6; untuk 𝑛 ≡ 0 𝑚𝑜𝑑 3 .
Keywords: Bilangan Kromatik, Pewarnaan Graceful, Operasi Comb Product

## ABSTRACT
Graceful  coloring  is  a  combination  of  the  concepts  of  graceful  and  node  coloring.  Graceful coloring is defined as labeling a vertex of a graph G that satisfies an injective function from the set of vertices to the set of non-negative integers {1, 2, … , 𝑘} such that each edge uv in G gets labeled |𝑐(𝑢) − 𝑐(𝑣)| , then the label of each side will be different. This study aims to determine the graceful coloring  and  chromatic  numbers  on  a  graph (𝐶 𝑛 ▷ 𝑆 𝑚 ) .  This  research  is  a  type  of exploratory research  using  axiomatic  deductive  methods  and  pattern  detection  methods.  This  research produces a theorem about graceful coloring on cycle graphs of comb graph star which consists of three  cases,  namely 𝜒 𝑔 (𝐶 𝑛 ▷ 𝑆 𝑚 ) = 𝑚 + 6; for 𝑛 ≡ 1 𝑚𝑜𝑑 3 , 𝜒 𝑔 (𝐶 𝑛 ▷ 𝑆 𝑚 ) = 𝑚 + 6; for 𝑛 ≡ 2 𝑚𝑜𝑑 3 , and 𝜒 𝑔 (𝐶 𝑛 ▷ 𝑆 𝑚 ) = 𝑚 + 6; for 𝑛 ≡ 0 𝑚𝑜𝑑 3 .

## Keywords: Chromatic Number, Graceful Coloring, Comb Product Operation

## PENDAHULUAN
Sebagai ilmu dasar disiplin ilmu, matematika berperan penting dalam perkembangan ilmu  pengetahuan,  teknologi  modern,  dan  kemampuan  berpikir  manusia.  Teknologi  yang mengikuti  perkembangan  zaman  menuntut  manusia  untuk  menghadapi  masalah  yang
semakin  kompleks.  Pemecahan  masalah  yang  semakin  kompleks,  manusia  dituntut  untuk dapat  menyelesaikannya  secara  logis.  Peran  matematika  adalah  untuk  memberi  manusia pengetahuan tentang bagaimana menangani masalah, memodelkannya, mengamati akarnya secara koherensi, dan membuatnya mudah dipecahkan. Salah satu cabang matematika yang diterapkan dalam setiap bidang ilmu dalam kehidupan sehari-hari adalah teori graf. [13].
Salah satu cabang ilmu matematika yang mempelajari sifat-sifat graf disebut teori graf. Graf 𝐺 adalah  pasangan  himpunan (𝑉(𝐺), 𝐸(𝐺)) dimana 𝑉(𝐺) merupakan  himpunan  tak kosong dari objek-objek yang disimbolkan dengan ( vertex ) dan 𝐸(𝐺) adalah himpunan yang mungkin kosong dari pasangan tak terurut (𝑢, 𝑣) dari simpul-simpul 𝑢 dan 𝑣 yang berbeda di 𝑉(𝐺) yang  dinotasikan  dengan  ( edge ).(Fierera  &  Sugeng,  2022)[7].  Teori  graf  ini menjelaskan  adanya  hubungan  dan  pasangan  pada  simpul-simpul  tertentu  seperti  pada kehidupan  yaitu  hubungan  antar  manusia  dengan  ketakwaannya  kepada  Allah  SWT  dan hubungan antar sesama manusia, misalnya hubungan laki-laki dan perempuan yang sengaja diciptakan berpasang-pasangan. Seperti dalam firman Allah SWT dalam surat Yasin  ayat 36:
َ ن ٰحْبُس َْيِذَّلا َ ق ل خ َ جا  و ْز  ْلْا ا هَّلُك اَّمِم َُتِبْْۢنُت َُض ْر  ْلْا َْن ِم  و َْمِهِسُفْن ا اَّمِم  و َ لْ َ ن ْوُم لْع ي . ٣٦ Artinya:َ “Mahasuciَ (Allah)َ yangَ telahَ menciptakanَ semuanyaَ berpasang-pasangan,  baik dari apa yang ditumbuhkan oleh bumi dan dari diri mereka sendiri, maupun dari apa yang tidak mereka ketahui.”
Ayat di atas adalah jawaban atas kedurhakaan orang-orang kafir di ayat sebelumnya. Ini  menggarisbawahi  bahwa  Allah  SWT  Maha  Suci,  Tuhan  yang  menciptakan  semua tanaman  dan  menciptakan  pasangan  bagi  setiap  tanaman  untuk  menghasilkan  buah.  Oleh karena  itu,  Allah  SWT  Sang  Pencipta  Maha  suci  atas  segala  kekurangan  dan  sifat  buruk. Dapat disimpulkan bahwa Allah sudah menciptakan segala sesuatu baik benda hidup atau mati secara berpasang-pasangan, ada siang dan malam, ada suka dan duka, ada suami dan istri, ada  hidup  dan mati  dan begitu pula seterusnya agar mereka beriman kepada Allah. Sama halnya seperti graf yang memiliki hubungan antara simpul dan sisi sehingga terbentuk pasangan himpunan (𝑉(𝐺), 𝐸(𝐺)) [9].
Teori  graf  pertama  kali  dirumuskan  oleh  matematikawan  dan  fisikawan  Swiss Leonhard  Euler  pada  tahun  1736  dalam  idenya  untuk  memecahkan  masalah  jembatan Königsberg.  Dipahami  bahwa  "kota  Königsberg  (sekarang  dikenal  sebagai  Klingler)  di Prusia timur, Jerman, memiliki  sungai  bernama  Pregar.  Kota Königsberg terbagi  menjadi empat daratan. Ada tujuh jembatan di sungai yang menghubungkan empat tempat tersebut. Permasalahan jembatan Königsberg yang terkenal adalah "Mungkinkah seseorang memulai dari benua tertentu, melewati masing-masing dari tujuh jembatan tepat satu kali, dan kembali ke  daratan  asalnya?  Jawaban  Euler  tertulis  dalam  bukunya  yang  berjudul  "Solutio Problematis ad Geometriam Pertinentis Site"[5].
Masalah  Konisberg  Bridge  menjadi  dasar  munculnya  masalah  dalam  dunia  graf. Seiring  berkembangnya  zaman,  perkembangan  grafis  juga  sangat  pesat.  Matematikawan mempelajari pengetahuan yang berkaitan dengan teori graf untuk mendapatkan pengetahuan dan penerapannya dalam kehidupan. Salah satu topik yang berkembang pesat dalam teori graf  adalah  pewarnaan  graf.  Pewarnaan  graf  adalah  metode  pelabelan  graf  dengan memberikan warna pada simpul, sisi, atau daerah yang berdekatan. Terdapat banyak macam pewarnaan  graf  diantaranya  pewarnaan  simpul  proper,  pewarnaan  ketakteraturan,  dan pewarnaan graceful.
Penelitian  ini  membahas  tentang  pewarnaan graceful .  Pada  penelitian  sebelumnya, English dan Zhang, 2017 [6] menemukan bilangan kromatik pada graf pohon. Khoirunnisa et  al.,  2021  [10]  menemukan  bilangan  kromatik  dari  hasil  penggabungan  graf  tangga.
Kristiana et  al., 2022 [11] menemukan bilangan  kromatik dari penggabungan simpul  dari graf keluarga pohon. Selain itu, Zhang, 2016 [15] mendefinisikan pewarnaan graceful pada graf  dan  memperoleh  bilangan  kromatik  dari  beberapa  graf.  Berdasarkan  hasil  penelitian sebelumnya,  para  peneliti  tertarik  untuk  memahami  lebih  jauh  pewarnaan graceful pada (𝐶 𝑛 ▷ 𝑆 𝑚 ) .  Berdasarkan  penelitian  sebelumnya,  peneliti  tertarik  untuk  menganalisis bilangan kromatik graceful pada graf siklus comb graf star sehingga nantinya peneliti akan mendapatkan  bilangan  kromatik graceful berpola  dan  dengan  demikian  memperoleh teorema baru. Berikut merupakan Lema pewarnaan graceful : Lema 1.1 𝜒 𝑔 (𝐺) ≥ ∆(𝐺) + 1

## METODE PENELITIAN
Penelitian  ini  merupakan  jenis  penelitian  kualitatif  eksploratif.  Penelitian  yang dilakukan secara luas dan mendalam yang bertujuan untuk mengkaji dan menelaah hal baru yang kemudian hasil dari penelitiannya dapat menjadi acuan penelitian berikutnya disebut dengan  penelitian  eksploratif.  Sebab  mengapa  penelitian  ini  merupakan  penelitian eksploratif karena tujuan dari penelitian ini adalah untuk mengenalkan suatu hal baru agar lebih dikenal oleh masyarakat luas serta memberikan gambaran dasar dan mengembangkan teori yang bersifat dapat diperbaharui.
Metode yang digunakan dalam penelitian ini adalah metode deduktif aksiomatik dan metode  pendeteksi  pola.  Metode  deduktif  aksiomatik  adalah  metode  penelitian  yang menggunakna prinsip-prinsip pembuktian deduktif yang berlaku dalam logika matematika dengan menggunakan aksioma atau teorema yang sudah ada, kemudian diterapkan dalam pewarnaan graceful dari (𝐶 𝑛 ▷ 𝑆 𝑚 ) . Kemudian, metode pendeteksi pola digunakan untuk mencari pola dan menentukan bilangan kromatik graceful pada (𝐶 𝑛 ▷ 𝑆 𝑚 ).
Penelitian ini bertujuan untuk mengetahui pewarnaan graceful dan kromatik graceful pada graf siklus comb graf star . Langkah pertama yang dilakukan dalam penelitian ini adalah mengidentifikasi  graf  yang  akan  diteliti  yaitu  graf  siklus comb graf star (𝐶 𝑛 ▷ 𝑆 𝑚 ) . Kemudian menentukan kardinalitas dari graf tersebut.
Langkah  kedua,  melakukan  pewarnaan  simpul  dengan  warna  paling  kecil  dimana antara  simpul  yang  berdekatan  harus  memuat  warna  yang  berbeda.  Selain  itu,  gunakan definisi dari pewarnaan graceful yaitu warna sisi diperoleh dari selisih nilai mutlak antara dua simpul yang bertetangga untuk melakukan pewarnaan sisi pada graf. Lalu melakukan pengecekan warna sisi yang diperoleh, apabila terdapat dua sisi yang bertetangga memiliki warna yang sama, maka harus kembali ke tahap pertama dalam pewarnaan simpul pada graf yang diteliti. Apabila setiap warna sisi yang bertetangga memuat warna berbeda dan sesuai dengan definisi pewarnaan graceful , maka dapat dilanjutkan ke tahap berikutnya. Langkah  ketiga  adalah  menentukan  bilangan  kromatik graceful 𝜒 𝑔 (𝐶 𝑛 ▷ 𝑆 𝑚 ) .  Hal pertama  yang  harus  dilakukan  dalam  menentukan  bilangan  kromatik graceful yaitu melakukan  pewarnaan  simpul.  Kemudian,  pewarnaan  sisi  didapatkan  dari  selisih  nilai mutlak dari warna simpul pada setiap sisinya. Selain itu, perlu dipastikan warna simpul pada setiap graf sudah seminimal mungkin, artinya warna yang disusun merupakan warna paling kecil sehingga itulah yang disebut bilangan kromatik graceful . Sebelumnya, pada penelitian ini telah mencari bilangan kromatik 𝜒 𝑔 (𝐶 𝑛 ▷ 𝑆 𝑚 ) dari graf yang diteliti untuk mengetahui minimal  bilangan  kromatik graceful yang  akan  diperoleh.  Hasil  yang  diperoleh menunjukkan bahwa bilangan kromatik graceful lebih besar daripada bilangan kromatik dari graf siklus comb graf star yang diteliti. Hal ini dikarenakan dalam pewarnaan simpul hanya memperhatikan  setiap  simpul  yang  bertetangga  memiliki  warna  berbeda.  Berbeda  halnya dengan  pewarnaan  titik graceful ,  yaitu  tidak  hanya  memperhatikan  setiap  simpul  yang bertetangga harus memiliki warna berbeda, tetapi juga perlu memperhatikan warna sisinya
yang  diperoleh  dari  nilai  mutlak  selisih  simpul  yang  bertetangga  dimana  setiap  sisi  yang bertetangga harus memiliki warna yang berbeda pula.
Langkah keempat, menentukan teorema hasil pewarnaan graceful . Dalam menentukan teorema ini, hal yang dilakukan adalah menentukan batas atas dan batas bawah simpul pola pewarnaan pada setiap graf yang diteliti. Jika grafnya memiliki satu pola pewarnaan yang bisa diteruskan hingga 𝑛 simpul, maka teorema yang terbentuk hanya satu kasus pembuktian teorema  saja.  Akan  tetapi,  jika  graf  yang  diteliti  membutuhkan  lebih  dari  satu  pola pewarnaan untuk bisa diwarnai hingga 𝑛 simpul, maka teorema yang terbentuk lebih dari satu kasus pembuktian. Kemudian, pada penelitian ini memperoleh satu teorema baru yaitu bilangan kromatik graceful pada graf siklus comb graf star .

## HASIL DAN PEMBAHASAN
Berikut  ini  merupakan  penjelasan  dari  hasil  penelitian  dengan  proses  pencarian bilangan  kromatik graceful pada (𝐶 𝑛 ▷ 𝑆 𝑚 ) .  Hasil  penelitian  ini  ialah  berupa  teorema bilangan  kromatik graceful pada (𝐶 𝑛 ▷ 𝑆 𝑚 ) .  Langkah  awal  pada  penelitian  ini  dengan menentukan  graf  yang  akan  diteliti  yaitu  graf (𝐶 𝑛 ▷ 𝑆 𝑚 ) .  Selanjutnya  menentukan kardinalitas dari graf tersebut. Lalu melakukan pewarnaan simpul dan pewarnaan sisi pada graf yang telah ditentukan sedemikian hingga memenuhi definisi pewarnaan graceful dan dapat menghasilkan bilangan kromatiknya.

## Gambar 1 Prosedur Penelitian
Pada  penelitian  ini  ditemukan  satu  teorema  yang  terdiri  dari  tiga  kasus  baru  terkait pewarnaan graceful pada graf siklus comb graf star . Penyajian hasil teorema pada penelitian ini  disajikan  dengan  pernyataan  yang  disertai  pembuktian  sebagai  validasi  kebenaran teorema tersebut.
A. Hasil
Pada  penelitian  pewarnaan graceful pada  graf  siklus comb graf star (𝐶 𝑛 ▷ 𝑆 𝑚 ) ini diperoleh satu teorema. Pewarnaan ini dimulai dari memberikan warna pada setiap simpul dan sisi sedemikian hingga setiap dua simpul yang bertetangga berbeda dan setiap dua sisi yang bertetangga berbeda, dimana warna sisi diperoleh dari selisih warna dua simpul yang berkaitan  dengan  sisi  tersebut.  Banyaknya  warna  minimum  yang  digunakan  dalam pewarnaan simpul proper disebut bilangan kromatik graceful dari graf 𝐺 yang dinotasikan dengan 𝜒 𝑔 (𝐺) . Jadi, bilangan kromatik graceful adalah bilangan 𝑘 terkecil sehingga graf 𝐺 dapat diwarnai dengan 𝑘 warna.
Teorema 3.1. Bilangan kromatik graceful pada star (𝐶 𝑛 ▷ 𝑆 𝑚 ) adalah:
𝜒 𝑔 (𝐶 𝑛 ▷ 𝑆 𝑚 ) = 𝑚 + 6
Bukti. Graf siklus comb graf star (𝐶 𝑛 ▷ 𝑆 𝑚 ) memiliki 𝑉(𝐶 𝑛 ▷ 𝑆 𝑚 ) = {𝑥 𝑖 ; 1 ≤ 𝑖 ≤ 2𝑛} ∪ {𝑦 𝑗 ; 1 ≤ 𝑗 ≤ 𝑚} dan 𝐸(𝐶 𝑛 ▷ 𝑆 𝑚 ) = {𝑥 𝑖 𝑥 𝑖+1 ; 1 ≤ 𝑖 ≤ 𝑛 − 1} ∪ {𝑥 𝑛 𝑥 1 } ∪ {𝑥 𝑖 𝑦 𝑗 ; 1 ≤ 𝑖 ≤ 𝑛, 1 ≤ 𝑗 ≤ 𝑚, 𝑖 = 𝑔𝑎𝑛𝑗𝑖𝑙}. Kardinalitas simpul dari graf (𝐶 𝑛 ▷ 𝑆 𝑚 ) adalah |𝑉(𝐶 𝑛 ▷ 𝑆 𝑚 )| = 𝑛 (1 + 𝑚 2 ) dan  kardinalitas  sisi  dari  graf (𝐶 𝑛 ▷ 𝑆 𝑚 ) adalah |𝐸(𝐶 𝑛 ▷ 𝑆 𝑚 )| = 𝑛 (1 + 𝑚 2 ) . Derajat simpul dari graf (𝐶 𝑛 ▷ 𝑆 𝑚 ) adalah ∆(𝐶 𝑛 ▷ 𝑆 𝑚 ) = 𝑚 + 2.
Gambar 2 Graf (𝑪 𝟕 ▷ 𝑺 𝟗 ).
Kasus 1. Untuk 𝑛 ≡ 1 𝑚𝑜𝑑 3
Langkah  pertama  untuk  membuktikan 𝜒 𝑔 (𝐶 𝑛 ▷ 𝑆 𝑚 ) = 𝑚 + 6; untuk 𝑛 ≡ 1 𝑚𝑜𝑑 3 , harus  ditentukan  terlebih  dahulu  batas  bawah  dan  batas  atasnya.  Berdasarkan  Lema  1.1 𝜒 𝑔 (𝐺) ≥ Δ(𝐺) + 1 diperoleh batas bawah 𝜒 𝑔 (𝐶 𝑛 ▷ 𝑆 𝑚 ) ≥ 𝑚 + 3. Diasumsikan 𝜒 𝑔 (𝐺) = 𝑚 + 5 ,  Diberikan  warna  simpul 𝑦 𝑚 = 𝑚 + 5 ,  diperoleh  sisi 𝑥 5 𝑦 9 yang  akan  memiliki warna yang sama dengan sisi 𝑥 5 𝑦 1 , hal ini kontradiksi dengan definisi pewarnaan graceful
𝐶 7 ▷ 𝑆 9
sedemikian  hingga  asumsi  terdapat 𝑚 + 5 warna  adalah  salah,  terbukti  bahwa 𝜒 𝑔 (𝐶 𝑛 ▷ 𝑆 𝑚 ) ≥ 𝑚 + 6 .
Berikutnya  akan  dibuktikan  batas  atas  bilangan  kromatik 𝜒 𝑔 (𝐶 𝑛 ▷ 𝑆 𝑚 ) ≤ 𝑚 + 5 . Pewarnaan simpul proper 𝑓: 𝑉(𝐶 𝑛 ▷ 𝑆 𝑚 ) → {1, 2, 3, … , 𝑚 + 6} diberikan oleh: Untuk 𝑛 ≡ 1 𝑚𝑜𝑑 3
𝑓[𝑐(𝑦 𝑗 )]
{ 1, 𝑢𝑛𝑡𝑢𝑘 𝑖 ≡ 1 𝑚𝑜𝑑 3 4, 𝑢𝑛𝑡𝑢𝑘 𝑖  ≡  2 𝑚𝑜𝑑  3 2, 𝑢𝑛𝑡𝑢𝑘 𝑖  ≡  0 𝑚𝑜𝑑 3 3, 𝑢𝑛𝑡𝑢𝑘 𝑖 = 𝑛 − 1 5, 𝑢𝑛𝑡𝑢𝑘 𝑖 = 𝑛 𝑓[𝑐(𝑦 𝑗 )] { 𝑚 + 3 𝑢𝑛𝑡𝑢𝑘 3 ≤ 𝑗 ≤ 𝑚 2 𝑢𝑛𝑡𝑢𝑘 𝑗 = 1 3 𝑢𝑛𝑡𝑢𝑘 𝑗 = 2 𝐾𝑎𝑠𝑢𝑠 1 𝑓[𝑐(𝑦 𝑗 )] {𝑚 + 4 𝑢𝑛𝑡𝑢𝑘 1 ≤ 𝑗 ≤ 𝑚 Kasus 2
𝑓[𝑐(𝑦 𝑗 )] { 𝑚 + 6 𝑢𝑛𝑡𝑢𝑘 2 ≤ 𝑗 ≤ 𝑚 3 𝑢𝑛𝑡𝑢𝑘 𝑗 = 1
Kasus 3 𝑓[𝑐(𝑦 𝑗 )] {𝑚 + 5 𝑢𝑛𝑡𝑢𝑘 1 ≤ 𝑗 ≤ 𝑚 Kasus 4
Dapat dilihat bahwa fungsi 𝑓 juga menginduksi pewarnaan sisi proper dari graf (𝐶 𝑛 ▷ 𝑆 𝑚 ) diberikan oleh:
𝑓[𝑐 ′ (𝑥 𝑖 𝑥 𝑖+1 )] { 3; 𝑢𝑛𝑡𝑢𝑘 𝑖 ≡ 1 𝑚𝑜𝑑 3 2; 𝑢𝑛𝑡𝑢𝑘 𝑖 ≡ 2 𝑚𝑜𝑑 3 1; 𝑢𝑛𝑡𝑢𝑘 𝑖  ≡  0 𝑚𝑜𝑑 3 2; 𝑢𝑛𝑡𝑢𝑘 𝑖 = 𝑛 − 1 4; 𝑢𝑛𝑡𝑢𝑘 𝑖 = 𝑛
𝑓[𝑐 ′ (𝑥 𝑖 𝑦 𝑗 )] { 𝑚 + 2 𝑢𝑛𝑡𝑢𝑘 1 ≤ 𝑗 ≤ 𝑚 1 𝑢𝑛𝑡𝑢𝑘 𝑗 = 1 2 𝑢𝑛𝑡𝑢𝑘 𝑗 = 2 𝐾𝑎𝑠𝑢𝑠 1
𝑓[𝑐 ′ (𝑥 𝑖 𝑦 𝑗 )] { 𝑚 + 2 𝑢𝑛𝑡𝑢𝑘 2 ≤ 𝑗 ≤ 𝑚, 𝑖 ≥ 2 3 𝑢𝑛𝑡𝑢𝑘 𝑖 ≡ 0 𝑚𝑜𝑑 3 1 𝑢𝑛𝑡𝑢𝑘 𝑖 ≡ 1 𝑚𝑜𝑑 3 2 𝑢𝑛𝑡𝑢𝑘 𝑖 ≡ 2 𝑚𝑜𝑑 3 𝐾𝑎𝑠𝑢𝑠 2
𝑓[𝑐 ′ (𝑥 𝑖 𝑦 𝑗 )]{𝑚 + 2 𝑢𝑛𝑡𝑢𝑘 1 ≤ 𝑗 ≤ 𝑚                                                         𝐾𝑎𝑠𝑢𝑠 3
Berdasarkan batas bawah dan batas atas bilangan kromatik graceful pada graf 𝐶 𝑛 ▷ 𝑆 𝑚 diperoleh 𝑚 + 6 ≥ 𝜒 𝑔 (𝐶 𝑛 ▷ 𝑆 𝑚 ) ≥ 𝑚 + 6 , dengan kata lain 𝜒 𝑔 (𝐶 𝑛 ▷ 𝑆 𝑚 ) = 𝑚 + 6; untuk 𝑛 ≡ 1 𝑚𝑜𝑑 3 . Kasus 2. Untuk 𝑛 ≡ 2 𝑚𝑜𝑑 3
Langkah  pertama  untuk  membuktikan 𝜒 𝑔 (𝐶 𝑛 ▷ 𝑆 𝑚 ) = 𝑚 + 6; untuk 𝑛 ≡ 2 𝑚𝑜𝑑 3 , harus  ditentukan  terlebih  dahulu  batas  bawah  dan  batas  atasnya.  Berdasarkan  Lema  1.1
𝜒 𝑔 (𝐺) ≥ Δ(𝐺) + 1 diperoleh batas bawah 𝜒 𝑔 (𝐶 𝑛 ▷ 𝑆 𝑚 ) ≥ 𝑚 + 3. Diasumsikan 𝜒 𝑔 (𝐺) = 𝑚 + 5 ,  Diberikan  warna  simpul 𝑦 𝑚 = 𝑚 + 5 ,  diperoleh  sisi 𝑥 5 𝑦 9 yang  akan  memiliki warna yang sama dengan sisi 𝑥 5 𝑦 1 , hal ini kontradiksi dengan definisi pewarnaan graceful sedemikian  hingga  asumsi  terdapat 𝑚 + 5 warna  adalah  salah,  terbukti  bahwa 𝜒 𝑔 (𝐶 𝑛 ▷ 𝑆 𝑚 ) ≥ 𝑚 + 6 .
Berikutnya  akan  dibuktikan  batas  atas  bilangan  kromatik 𝜒 𝑔 (𝐶 𝑛 ▷ 𝑆 𝑚 ) ≤ 𝑚 + 5 . Pewarnaan simpul proper 𝑓: 𝑉(𝐶 𝑛 ▷ 𝑆 𝑚 ) → {1, 2, 3, … , 𝑚 + 6} diberikan oleh: Untuk 𝑛 ≡ 2 𝑚𝑜𝑑 3
𝑓[𝑐(𝑦 𝑗 )] { 1, 𝑢𝑛𝑡𝑢𝑘 𝑖 ≡ 1 𝑚𝑜𝑑 3
4, 𝑢𝑛𝑡𝑢𝑘 𝑖 ≡ 2 𝑚𝑜𝑑 3 2, 𝑢𝑛𝑡𝑢𝑘 𝑖 ≡ 0 𝑚𝑜𝑑 3 3, 𝑢𝑛𝑡𝑢𝑘 𝑖 = 𝑛 𝑓[𝑐(𝑦 𝑗 )] { 𝑚 + 3 𝑢𝑛𝑡𝑢𝑘 2 ≤ 𝑗 ≤ 𝑚 2 𝑢𝑛𝑡𝑢𝑘 𝑗 = 1
Kasus 1
𝑓[𝑐(𝑦 𝑗 )]{𝑚 + 4 𝑢𝑛𝑡𝑢𝑘 1 ≤ 𝑗 ≤ 𝑚 Kasus 2
𝑓[𝑐(𝑦 𝑗 )] { 𝑚 + 6 𝑢𝑛𝑡𝑢𝑘 2 ≤ 𝑗 ≤ 𝑚 3 𝑢𝑛𝑡𝑢𝑘 𝑗 = 1 Kasus 3
𝑓[𝑐(𝑦 𝑗 )] { 𝑚 + 3 𝑢𝑛𝑡𝑢𝑘 2 ≤ 𝑗 ≤ 𝑚 3 𝑢𝑛𝑡𝑢𝑘 𝑗 = 1

## Kasus 4
Dapat dilihat bahwa fungsi 𝑓 juga menginduksi pewarnaan sisi proper dari graf (𝐶 𝑛 ▷ 𝑆 𝑚 ) diberikan oleh:
𝑓[𝑐 ′ (𝑥 𝑖 𝑥 𝑖+1 )] { 3, 𝑢𝑛𝑡𝑢𝑘 𝑖 ≡ 1 𝑚𝑜𝑑 3 2, 𝑢𝑛𝑡𝑢𝑘 𝑖 ≡ 2 𝑚𝑜𝑑 3
1, 𝑢𝑛𝑡𝑢𝑘 𝑖 ≡ 0 𝑚𝑜𝑑 3 2, 𝑢𝑛𝑡𝑢𝑘 𝑖 = 𝑛
𝑓[𝑐 ′ (𝑥 𝑖 𝑦 𝑗 )] { 𝑚 + 2 𝑢𝑛𝑡𝑢𝑘 2 ≤ 𝑗 ≤ 𝑚, 𝑖 ≥ 2 1; 𝑢𝑛𝑡𝑢𝑘 𝑖  ≡  1 𝑚𝑜𝑑 3 1; 𝑢𝑛𝑡𝑢𝑘 𝑖  ≡  2 𝑚𝑜𝑑 3 3; 𝑢𝑛𝑡𝑢𝑘 𝑖  ≡  0 𝑚𝑜𝑑 3 2; 𝑢𝑛𝑡𝑢𝑘 𝑖  ≡ 1 𝑚𝑜𝑑 3
Berdasarkan batas bawah dan batas atas bilangan kromatik graceful pada graf 𝐶 𝑛 ▷ 𝑆 𝑚 diperoleh 𝑚 + 6 ≥ 𝜒 𝑔 (𝐶 𝑛 ▷ 𝑆 𝑚 ) ≥ 𝑚 + 6 , dengan kata lain 𝜒 𝑔 (𝐶 𝑛 ▷ 𝑆 𝑚 ) = 𝑚 + 6; untuk 𝑛 ≡ 2 𝑚𝑜𝑑 3 . Kasus 3. Untuk 𝑛 ≡ 0 𝑚𝑜𝑑 3
Langkah  pertama  untuk  membuktikan 𝜒 𝑔 (𝐶 𝑛 ▷ 𝑆 𝑚 ) = 𝑚 + 6; untuk 𝑛 ≡ 0 𝑚𝑜𝑑 3 , harus  ditentukan  terlebih  dahulu  batas  bawah  dan  batas  atasnya.  Berdasarkan  Lema  1.1 𝜒 𝑔 (𝐺) ≥ Δ(𝐺) + 1 diperoleh batas bawah 𝜒 𝑔 (𝐶 𝑛 ▷ 𝑆 𝑚 ) ≥ 𝑚 + 3. Diasumsikan 𝜒 𝑔 (𝐺) = 𝑚 + 5 ,  Diberikan  warna  simpul 𝑦 𝑚 = 𝑚 + 5 ,  diperoleh  sisi 𝑥 5 𝑦 9 yang  akan  memiliki warna yang sama dengan sisi 𝑥 5 𝑦 1 , hal ini kontradiksi dengan definisi pewarnaan graceful
sedemikian  hingga  asumsi  terdapat 𝑚 + 5 warna  adalah  salah,  terbukti  bahwa 𝜒 𝑔 (𝐶 𝑛 ▷ 𝑆 𝑚 ) ≥ 𝑚 + 6 .
Berikutnya  akan  dibuktikan  batas  atas  bilangan  kromatik 𝜒 𝑔 (𝐶 𝑛 ▷ 𝑆 𝑚 ) ≤ 𝑚 + 5 . Pewarnaan simpul proper 𝑓: 𝑉(𝐶 𝑛 ▷ 𝑆 𝑚 ) → {1, 2, 3, … , 𝑚 + 6} diberikan oleh: Untuk 𝑛 ≡ 0 𝑚𝑜𝑑 3
𝑓[𝑐(𝑦 𝑗 )] { 1; 𝑢𝑛𝑡𝑢𝑘 𝑖 ≡ 1 𝑚𝑜𝑑 3 4; 𝑢𝑛𝑡𝑢𝑘 𝑖 ≡ 2 𝑚𝑜𝑑 3 2; 𝑢𝑛𝑡𝑢𝑘 𝑖 ≡ 0 𝑚𝑜𝑑 3
𝑓[𝑐(𝑦 𝑗 )] { 𝑚 + 3 𝑢𝑛𝑡𝑢𝑘 2 ≤ 𝑗 ≤ 𝑚 3 𝑢𝑛𝑡𝑢𝑘 𝑗 = 1
Kasus 1
𝑓[𝑐(𝑦 𝑗 )]{𝑚 + 4 𝑢𝑛𝑡𝑢𝑘 1 ≤ 𝑗 ≤ 𝑚 Kasus 2
𝑓[𝑐(𝑦 𝑗 )] { 𝑚 + 6 𝑢𝑛𝑡𝑢𝑘 2 ≤ 𝑗 ≤ 𝑚 3 𝑢𝑛𝑡𝑢𝑘 𝑗 = 1

## Kasus 3
Dapat dilihat bahwa fungsi 𝑓 juga menginduksi pewarnaan sisi proper dari graf (𝐶 𝑛 ▷ 𝑆 𝑚 ) diberikan oleh:
𝑓[𝑐 ′ (𝑥 𝑖 𝑥 𝑖+1 )] { 3; 𝑢𝑛𝑡𝑢𝑘 𝑖 ≡ 1 𝑚𝑜𝑑 3 2; 𝑢𝑛𝑡𝑢𝑘 𝑖 ≡ 2 𝑚𝑜𝑑 3
1; 𝑢𝑛𝑡𝑢𝑘 𝑖 ≡ 0 𝑚𝑜𝑑 3
𝑓[𝑐 ′ (𝑥 𝑖 𝑦 𝑗 )] { 𝑚 + 3 , 𝑢𝑛𝑡𝑢𝑘 1  ≤ 𝑗 ≤ 𝑚 , 𝑖 ≥ 2 2  , 𝑢𝑛𝑡𝑢𝑘  𝑖 ≡ 1 𝑚𝑜𝑑 3 3  , 𝑢𝑛𝑡𝑢𝑘  𝑖 ≡ 0 𝑚𝑜𝑑 3 1  , 𝑢𝑛𝑡𝑢𝑘 𝑖   ≡ 2 𝑚𝑜𝑑 3
Berdasarkan batas bawah dan batas atas bilangan kromatik graceful pada graf 𝐶 𝑛 ▷ 𝑆 𝑚 diperoleh 𝑚 + 6 ≥ 𝜒 𝑔 (𝐶 𝑛 ▷ 𝑆 𝑚 ) ≥ 𝑚 + 6 , dengan kata lain 𝜒 𝑔 (𝐶 𝑛 ▷ 𝑆 𝑚 ) = 𝑚 + 6; untuk 𝑛𝑡𝑢𝑘 𝑛 ≡ 0 𝑚𝑜𝑑 3 . B. Pembahasan
Penelitian ini menghasilkan satu teorema baru yakni :
𝜒 𝑔 (𝐶 𝑛 ▷ 𝑆 𝑚 ) = 𝑚 + 6
Langkah  pertama  pembuktian  teorema  ini  dengan  menentukan  batas  bawah menggunakan Lema 1.1 𝜒 𝑔 (𝐺) ≥ Δ(𝐺) + 1 . Diketahui Δ(𝐶 𝑛 ▷ 𝑆 𝑚 ) = 𝑚 + 2 , maka:
𝜒 𝑔 (𝐶 𝑛 ▷ 𝑆 𝑚 ) ≥ Δ(𝐶 𝑛 ▷ 𝑆 𝑚 ) + 1 𝜒 𝑔 (𝐶 𝑛 ▷ 𝑆 𝑚 ) ≥ 𝑚 + 2 + 1 𝜒 𝑔 (𝐶 𝑛 ▷ 𝑆 𝑚 ) ≥ 𝑚 + 3
Dikarenakan hasil teorema pada analisis graf (𝐶 𝑛 ▷ 𝑆 𝑚 ) adalah 𝜒 𝑔 (𝐶 𝑛 ▷ 𝑆 𝑚 ) = 𝑚 + 6 dan dari Lema 𝜒 𝑔 (𝐶 𝑛 ▷ 𝑆 𝑚 ) ≥ 𝑚 + 3 , maka diasumsikan 𝜒 𝑔 (𝐺) = 𝑚 + 5 .  Alasan  menggunakan  asumsi  tersebut  karena  mengambil  angka  yang  paling mendekati 𝑚 + 6 .  Kemudian  diberikan  warna  simpul 𝑦 𝑚 = 𝑚 + 5 yang  artinya 𝑦 9 = 14 diperoleh  sisi 𝑥 5 𝑦 9 yang  akan  memiliki  warna  yang  sama  dengan  sisi 𝑥 5 𝑦 1 ,  hal  ini
kontradiksi dengan definisi pewarnaan graceful sedemikian hingga asumsi terdapat 𝑚 + 5 warna adalah salah, terbukti bahwa 𝜒 𝑔 (𝐶 𝑛 ▷ 𝑆 𝑚 ) ≥ 𝑚 + 6 .
Pada  pembuktian  batas  terdapat 𝑓[𝑐(𝑦 𝑗 )] dan 𝑓[𝑐 ′ (𝑥 𝑖 𝑦 𝑗 )] yang  memuat  beberapa fungsi  yang  berbeda  pada  setiap 𝑛 modulonya,  sehingga  peneliti  membagi  ke  dalam beberapa kasus untuk memudahkan pembaca dalam memahaminya.

## KESIMPULAN
Berdasarkan hasil dan pembahasan analisis graf (𝐶 𝑛 ▷ 𝑆 𝑚 ) , dapat disimpulkan bahwa bilangan  kromatik graceful diperoleh  dengan  melakukan  pewarnaan  simpul    yang menginduksi pewarnaan sisi proper pada graf (𝐶 𝑛 ▷ 𝑆 𝑚 ) . Jadi, warna sisi pada pewarnaan graceful diperoleh dari hasil induksi atau selisih nilai mutlak simpul yang bertetangga pada sisi tersebut. Kemudian, diperoleh satu teorema baru yang terdiri dari tiga kasus mengenai pewarnaan graceful pada graf siklus comb graf star yaitu 𝜒 𝑔 (𝐶 𝑛 ▷ 𝑆 𝑚 ) = 𝑚 + 6; untuk 𝑛 ≡ 1 𝑚𝑜𝑑 3 , 𝜒 𝑔 (𝐶 𝑛 ▷ 𝑆 𝑚 ) = 𝑚 + 6; untuk 𝑛 ≡ 2 𝑚𝑜𝑑 3 , dan 𝜒 𝑔 (𝐶 𝑛 ▷ 𝑆 𝑚 ) = 𝑚 + 6; untuk 𝑛 ≡ 0 𝑚𝑜𝑑 3 .

## DAFTAR PUSTAKA
[1] Alfarisi, R., Dafik, Prihandini, R. M., Adawiyah, R., Albirri, E. R., & Agustin, I. H. (2019).  Graceful  Chromatic  Number  of  Unicyclic  Graphs. Journal  of  Physics: Conference Series . https://doi.org/10.1088/1742-6596/1306/1/012039
[2] Asy’Ari,َ M.َ L.,َ Dafik,َ Agustin,َ I.َ H.,َ Nisviasari,َ R.,َ &َ Adawiyah,َ R.َ (2022).َ Onَ graceful  chromatic  number  of  some  graphs. Journal  of  Physics:  Conference  Series . https://doi.org/10.1088/1742-6596/2157/1/012013
[3] Asy’ari,َ M.َ L.,َ Dafik,َ D.,َ &َ Tirta,َ I.َ M.َ (2022).َ Kerangkaَ Aktivitasَ Pembelajaranَ Berbasis  Riset  dengan  Pendekatan  STEM:  Penerapan  Materi  Pewarnaan  Graceful dalamَMeningkatkanَKemampuanَBerpikirَ….َ Ebook CGANT Universitas
[4] Bantara, J. A., Sudarsana, I. W., & Musdalifah, S. (2018). PELABELAN GRACEFUL GANJIL  PADA  GRAF  DUPLIKASI  DAN  SPLIT  BINTANG. JURNAL  ILMIAH MATEMATIKA
DAN TERAPAN .
https://doi.org/10.22487/2540766x.2018.v15.i1.10193
[5] Dafik. (2015). Teori Graf, Aplikasi dan Tumbuhnya Keterampilan Berpikir Tingkat Tinggi. In The conferment of professorship .
[6] English,  S.,  &  Zhang,  P.  (2017).  On  graceful  colorings  of  trees. Mathematica Bohemica . https://doi.org/10.21136/MB.2017.0035-15
[7] Fierera, A., & Sugeng, K. A. (2022). PEWARNAAN SIMPUL r-DINAMIS PADA GRAF  TERATAI  T_n. Pattimura  Proceeding:  Conference  of  Science  and Technology . https://doi.org/10.30598/pattimurasci.2021.knmxx.165-170
[8] Gross,  J.  L.,  Yellen,  J.,  &  Zhang,  P.  (2013).  Handbook  of  graph  theory.  Second Edition. In Journal of Development Economics .
[9] Ishartono, N. (2019). PENGGUNAAN GRAF POHON DALAM MENGAJARKAN KONSEP MAHRAM. Edukasia :  Jurnal  Penelitian  Pendidikan  Islam . https://doi.org/10.21043/edukasia.v14i2.4575
[10]  Khoirunnisa,  S.,  Dafik,  Kristiana,  A.  I.,  Alfarisi,  R.,  &  Albirri,  E.  R.  (2021).  On graceful  chromatic  number  of  comb  product  of  ladder  graph. Journal  of  Physics: Conference Series . https://doi.org/10.1088/1742-6596/1836/1/012027
[11]  Kristiana, A. I., Aji, A., Wihardjo, E., & Setiawan, D. (2022). on Graceful Chromatic Number  of  Vertex  amalgamation  of  Tree  Graph  Family. CAUCHY:  Jurnal Matematika Murni Dan Aplikasi . https://doi.org/10.18860/ca.v7i3.16334
[12]  Mincu, R., Obreja, C., & Popa, A. (2019). The Graceful Chromatic Number for Some
Particular Classes of Graphs. Proceedings - 21st International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2019 . https://doi.org/10.1109/SYNASC49474.2019.00024
[13]  Muzdalifa, A. (2016). Penerapan Graf Terhubung untuk Menentukan Klasifikasi Sidik Jari. Makalah IF2120 Matematika Diskrit – Sem. I Tahun 2016/2017 .
[14]  Sania, N. A., Dafik, D.,  &  Fatahillah, A.  (2020). Bilangan Kromatik  Graceful pada Keluarga  Graf  Unicyclic. CGANT  JOURNAL  OF  MATHEMATICS  AND APPLICATIONS . https://doi.org/10.25037/cgantjma.v1i2.39
[15]  Zhang,  P.  (2016).  A  kaleidoscopic  view  of  graph  colorings.  In SpringerBriefs  in Mathematics .