BILANGAN  KROMATIK  HARMONIS  PADA  GRAF PAYUNG,  GRAF PARASUT, DAN GRAF SEMI PARASUT
Fransiskus Fran 1*) Nilamsari Kusumastuti 2)
Robiandi 3)
1,2,3) Program Studi Matematika, Fakultas MIPA, Universitas Tanjungpura E-mail: fransiskusfran@math.untan.ac.id

## ABSTRACT
This article discusses the harmonic coloring of simple graphs 𝐺 , namely umbrella graphs, parachute graphs, and semi-parachute graphs. A vertex coloring on a graph 𝐺 is a harmonic coloring if each pair of colors (based on edges or pair of vertices) appears at most once. The chromatic number associated with the harmonic coloring of graph 𝐺 is called the harmonic chromatic number denoted 𝜒 𝐻 ( 𝐺 ) . In this article, the exact values of harmonic chromatic numbers are obtained for umbrella graphs, parachute graphs, and semi-parachute graphs.
Keywords: vertex coloring, pair of colors, chromatic number.

## ABSTRAK
Pada artikel ini dibahas pewarnaan harmonis pada suatu graf sederhana 𝐺 , yang merupakan graf payung, graf parasut dan graf semi parasut. Pewarnaan titik  pada graf 𝐺 merupakan pewarnaan harmonis jika masing- masing pasang warna (berdasarkan sisi atau pasangan titik) muncul maksimal satu kali. Bilangan kromatik yang terkait dengan pewarnaan harmonis pada graf 𝐺 disebut bilangan kromatik harmonis dilambangkan 𝜒 𝐻 ( 𝐺 ) . Pada artikel ini, diperoleh nilai eksak bilangan kromatik harmonis untuk graf payung, graf parasut, dan graf semi parasut.
Kata Kunci: pewarnaan titik, pasangan warna, bilangan kromatik.

## PENDAHULUAN
Teori  graf  merupakan  teori  yang  berkaitan  dengan  beberapa  cabang  ilmu  matematika  di antaranya  aljabar  dan  kombinatorika.  Permasalahan  yang terkait, dapat  diselesaikan salah  satunya dengan  terlebih  dahulu  mentransformasikan  masalah  tersebut  ke  dalam  graf,  menggunakan representasi titik dan garis. Kemudian, melakukan analisis yang sesuai berdasarkan konsep yang ada dalam teori graf.
Terdapat beberapa  kajian dalam teori graf, diantaranya terkait pewarnaan graf. Pada artikel ini, dibahas  pewarnaan  titik pada  graf  dengan  penambahan  syarat  tertentu  yang  disebut  pewarnaan harmonis. Konsep pewarnaan harmonis pada suatu graf dikemukakan oleh Harary dan Plantholt pada 1982.  Pewarnaan  harmonis  dikembangkan  berdasarkan  pewarnaan  titik  ( proper  vertex  coloring ) dengan  masing-masing  pasang  warna  maksimal  muncul  satu  kali.  Penelitian  terkait  pewarnaan harmonis pada beberapa  kelas graf telah dilakukan beberapa  peneliti, diantaranya pada middle graph dari 𝐶(𝐶 𝑛 ) , 𝐶(𝐾 1,𝑛 ) , dan 𝐶(𝑃 𝑛 ) (Vernold  Vivin & Akbar Ali, 2009), middle graph dari quadrilateral snake graphs (Mansuri & Chandel, 2021) , keluarga graf bintang ganda (Venkatachalam dkk., 2012),
pohon  (Aflaki dkk., 2016),  pohon  dengan  derajat  maksimum  (Akbari dkk., 2012),  graf ulat (Takaoka dkk.,  2015), graph  powers (Kierstead  dkk.,  2020) . Penelitian  lainnya  adalah  terkait  algoritma pewarnaan  harmonis  (Kolay dkk., 2016),  kasus khusus pewarnaan  harmonis, harmonis-1  (Liu  dkk., 2019), pewarnaan harmonis pada graf berarah  (Hegde & Castelino, 2015; Indriani & Budayasa, 2020) dan aplikasi pewarnaan harmonis (Selvi & Amutha, 2020).
Pada artikel ini, pewarnaan  harmonis secara khusus dibahas  untuk graf payung,  graf parasut, dan  graf  semi  parasut.  Masing-masing  graf  ini  merupakan  graf  yang  dibentuk  dari  graf  kipas  dan merupakan keluarga graf sederhana, terhubung, dan tak berarah. Graf payung 𝑈 𝑚,𝑛 adalah graf yang diperoleh  dengan  menggabungkan  graf  lintasan 𝑃 𝑛 pada  titik pusat  graf  kipas 𝐹 1,𝑚 (Ghodasara  & Patel, 2017; Rahmadi dkk., 2017). Himpunan titik graf  payung 𝑈 𝑚,𝑛 adalah 𝑉(𝑈 𝑚,𝑛 ) = {a, 𝑣 𝑖 , 𝑢 𝑗 | 𝑖 = 1,2, ⋯ , 𝑚 ; 𝑗 = 1,2, ⋯ , 𝑛 − 1} dan himpunan sisinya 𝐸(𝑈 𝑚,𝑛 ) = {(a, 𝑢 1 ), (a, 𝑣 𝑖 )| 𝑖 = 1,2, ⋯ , 𝑚}⋃{(𝑣 𝑖 ,𝑣 𝑖+1 ) | 𝑖 = 1,2, ⋯ , 𝑚 − 1}⋃{(𝑢 𝑗 ,𝑢 𝑗+1 ) | 𝑗 = 1,2, ⋯ , 𝑛 − 2} ,  sehingga  diperoleh bahwa |𝑉(𝑈 𝑚,𝑛 )| = 𝑚 + 𝑛 dan |𝐸(𝑈 𝑚,𝑛 )| = 2𝑚 + 𝑛 − 2 dengan ∆(𝑈 𝑚,𝑛 ) = 𝑚 + 1. Graf parasut dilambangkan 𝑃𝐶 𝑛 untuk 𝑛 ≥ 3 adalah  graf  dengan  himpunan  titik 𝑉(𝑃𝐶 𝑛 ) = {a, 𝑣 𝑖 , 𝑢 𝑗 | 𝑖, 𝑗 = 1,2, ⋯ , 𝑛 } dan himpunan sisinya adalah 𝐸(𝑃𝐶 𝑛 ) = {(a, 𝑣 𝑖 ), (𝑣 1 , 𝑢 1 ), (𝑣 𝑛 , 𝑢 𝑛 )| 𝑖 = 1,2, ⋯ , 𝑛}⋃{(𝑣 𝑖 , 𝑣 𝑖+1 ), (𝑢 𝑗 , 𝑢 𝑗+1 ) | 𝑖, 𝑗 = 1,2, ⋯ , 𝑛 − 1} . Nilai kardinalitas  untuk  himpunan  titik dan himpunan  sisi graf parasut adalah |𝑉(𝑃𝐶 𝑛 )| = 2𝑛 + 1  dan |𝐸(𝑃𝐶 𝑛 )| = 3𝑛 dengan ∆(𝑃𝐶 𝑛 ) = 𝑛 (Ponraj  dkk.,  2022).  Graf  semi  parasut  dinotasikan 𝑆𝑃 2𝑛−1 adalah  sebuah  graf  yang  memiliki himpunan  titik 𝑉(𝑆𝑃 2𝑛−1 ) = {a, 𝑣 𝑖 , 𝑢 𝑗 | 𝑖 = 1,2, ⋯ , 𝑛 dan 𝑗 = 1,2, ⋯ , 𝑛 − 1 } dan  himpunan  sisi 𝐸(𝑆𝑃 2𝑛−1 ) = {(a, 𝑣 𝑖 ), (𝑣 1 , 𝑣 𝑛 ), (𝑣 𝑗 , 𝑢 𝑗 ), (𝑢 𝑗 , 𝑣 𝑗+1 ) |  𝑖 = 1,2, ⋯ , 𝑛 dan 𝑗 = 1,2, ⋯ , 𝑛 − 1} sehingga nilai |𝑉(𝑆𝑃 2𝑛−1 )| = 2𝑛  dan |𝐸(𝑆𝑃 2𝑛−1 )| = 3𝑛 − 1 dengan ∆(𝑆𝑃 2𝑛−1 ) = 𝑛 (Aprilia  dkk., 2014). Dari ketiga graf tersebut, selanjutnya diterapkan pewarnaan  harmonis sehingga  diperoleh  nilai eksak bilangan kromatik harmonisnya.
Nilai eksak bilangan kromatik harmonis masing-masing graf (khususnya untuk kelas-kelas graf) tidak selalu dapat ditentukan dengan  mudah, hal ini  terkait dengan  karakteristik masing-masing graf, seperti  banyaknya  titik,  banyaknya  sisi,  ketetanggaan  antar  titik,  derajat  maksimum  titik,  dan parameter-parameter  lainnya. Oleh  karena  itu, pada  artikel ini, untuk graf payung 𝑈 𝑚,𝑛 , nilai eksak bilangan  kromatik harmonis ditentukan hanya untuk kondisi ketika 𝑚 ≥ 𝑛 . Untuk 𝑚 < 𝑛 diperlukan analisis lebih lanjut sehingga diperoleh  bilangan kromatik harmonisnya. Selain itu, pada artikel ini juga dibahas  alternatif pembuktian  untuk menunjukkan  nilai eksak bilangan  kromatik harmonis  pada  graf parasut yang sebelumnya telah diperoleh  dari penelitan lainnya (Huilgol & Sriram, 2016).
METODE
Metode  yang  digunakan  dalam  penelitian  ini  berupa  kajian  pustaka  terkait  teori  tentang pewarnaan  harmonis  pada  suatu  graf 𝐺 .  Teori  tersebut  diterapkan  pada  graf  payung 𝑈 𝑚,𝑛 ,  graf parasut 𝑃𝐶 𝑛 , dan  graf  semi parasut 𝑆𝑃 2𝑛−1 . Tahapan  yang dilakukan  untuk memperoleh  bilangan kromatik harmonis yaitu menerapkan  pewarnaan  titik pada graf payung 𝑈 𝑚,𝑛 , graf parasut 𝑃𝐶 𝑛 , dan graf semi parasut 𝑆𝑃 2𝑛−1 untuk beberapa  nilai 𝑛 yang berbeda.  Jika untuk setiap titik dengan  warna 𝑥 dan 𝑦 , pasangan  warna ( 𝑥, 𝑦) = (𝑦, 𝑥) untuk titik-titik bertetangga pada  graf berbeda, maka graf memenuhi  definisi pewarnaan  harmonis. Jika banyak  warna yang digunakan  sudah  minimum maka diperoleh  bilangan  kromatik  harmonis  untuk  graf  payung 𝑈 𝑚,𝑛 ,  graf  parasut 𝑃𝐶 𝑛 ,  dan  graf  semi parasut 𝑆𝑃 2𝑛−1 .  Kemudian  ditentukanlah  pola  pewarnaan  harmonis  pada  titik-titik untuk  masing- masing graf serta pola bilangan  kromatik harmonisnya  (untuk beberapa  nilai 𝑛 yang digunakan). Dari
pola  yang  terlihat,  diperoleh  rumus  bilangan  kromatik  harmonis  pada  masing-masing  graf  untuk memperoleh  nilai eksaknya.

## HASIL DAN PEMBAHASAN
Pada pewarnaan graf, terdapat masalah yang dikaji berupa  optimalisasi banyaknya warna yang digunakan  pada  pewarnaan  suatu graf 𝐺 . Banyaknya warna yang  optimal dapat  berarti  maksimum atau minimum, tergantung  pewarnaan  yang digunakan.  Untuk pewarnaan  titik, mensyaratkan bahwa titik-titik bertetangga di 𝐺 diwarnai dengan warna yang berbeda. Lebih lanjut, banyaknya warna yang optimal (minimum)  pada  pewarnaan  titik untuk graf 𝐺 disebut  bilangan  kromatik, dinotasikan 𝜒(𝐺) (Munir,  2010).  Selanjutnya,  berdasarkan  pewarnaan  titik, dapat  didefinisikan  pewarnaan  harmonis seperti dinyatakan yang pada Definisi 1.
Definisi 1 (Vernold Vivin & Akbar Ali, 2009) Diberikan graf sederhana 𝐺 = (𝑉(𝐺), 𝐸(𝐺)).
(i) Pewarnaan  harmonis  merupakan  pewarnaan  titik sehingga  pasangan-pasangan  warna  yang terbentuk, paling banyak muncul satu kali.
(ii) Bilangan  kromatik  harmonis  untuk  graf 𝐺 dilambangkan  dengan 𝜒 𝐻 (𝐺) ,  menyatakan  jumlah optimal (minimum) warna yang dapat digunakan pada pewarnaan harmonis.
Contoh
1 Diberikan graf 𝐺 dengan 𝑉(𝐺) = {𝑣 1 , 𝑣 2 , 𝑣 3 , 𝑣 4 } dan 𝐸(𝐺) = {(𝑣 1 , 𝑣 2 ), (𝑣 1 , 𝑣 3 ), (𝑣 1 , 𝑣 4 ), (𝑣 2 , 𝑣 4 )} . Graf 𝐺 tersebut dapat direpresentasikan dan diwarnai seperti pada Gambar 1.
(i) (i)
Gambar 1. Graf G dengan  Pewarnaan Harmonis
Berdasarkan Gambar  1, pewarnaan  pada graf 𝐺 menggunakan  label warna dengan  1,2,3, dan 4 serta memiliki |𝑉(𝐺)| = |𝐸(𝐺)| = 4 dengan χ 𝐻 (𝐺) = 4 . Berdasarkan Definisi 1(i), untuk masing- masing pasangan warna muncul maksimal 1 kali, yaitu (1,2), (1,3), (1,4) dan (2,4) . Hal ini berarti, pasangan  warna muncul setidaknya sebanyak sisi (pasangan  titik). Untuk graf tak berarah, diketahui bahwa  sisi (𝑢, 𝑣) = (𝑣, 𝑢) .  Akibatnya, untuk  warna 𝑥 dan 𝑦 ,  pasangan  warna ( 𝑥, 𝑦) = (𝑦, 𝑥) . Dengan  demikian,  untuk 𝑤 jenis  warna  dapat  diperoleh  banyaknya  pasangan  warna  berdasarkan kombinasi ( 𝑤 2 ) . Jika 𝐺 adalah graf dengan 𝑛 titik dan dapat diterapkan pewarnaan  harmonis dengan 𝑤 jenis warna, maka berlaku:
|𝐸(𝐺)| ≤ ( 𝑤 2 ) ⟺ |𝐸(𝐺)| ≤ 𝑤(𝑤−1) 2 (1)
Relasi (1)  selanjutnya  dapat  digunakan  utuk memperoleh  bilangan  kromatik harmonis  berdasarkan pewarnaan  harmonis yang dilakukan pada suatu graf.
Graf 𝐺 pada  Gambar  1 (a) memiliki titik yang berderajat  maksimum yaitu titik 𝑣 1 dinotasikan dengan 𝑑(𝑣 1 ) = 3 , akibatnya ∆(𝐺) = 3 .  Berdasarkan  Definisi 1(i),  jika titik 𝑣 1 diwarnai  dengan warna  1,  titik-titik  disekitar  (bertetangga  dengan) 𝑣 1 dapat  diwarnai  menggunakan  warna 2,3, ⋯ , ∆(𝐺) + 1. Pada pewarnaan  harmonis, jika ∆(𝐺) merupakan derajat maksimum pada graf 𝐺 dan graf 𝐺 dapat diwarnai dengan 𝑤 warna, maka berlaku:
𝑤 ≥ ∆(𝐺) + 1 (2) Relasi (2) dapat digunakan  sebagai batas bawah untuk menentukan bilangan kromatik harmonis. Selanjutnya, dapat ditentukan bilangan  kromatik harmonis  untuk graf payung, graf parasut dan graf semi parasut dengan memanfaatkan relasi pada (1) dan (2). Untuk masing-masing graf tersebut, bilangan kromatik harmonisnya dinyatakan pada Teorema 1 hingga Teorema 3. Secara khusus, untuk graf payung 𝑈 𝑚,𝑛 bilangan kromatik yang ditentukan hanya untuk kondisi ketika 𝑚 ≥ 𝑛 .
Teorema 1 Diberikan graf payung 𝑈 𝑚,𝑛 , maka χ 𝐻 (𝑈 𝑚,𝑛 ) = 𝑚 + 2, untuk 𝑚 ≥ 𝑛 . Bukti :
Diberikan  graf  payung 𝑈 𝑚,𝑛 , 𝑚 ≥ 𝑛 d engan 𝑉(𝑈 𝑚,𝑛 ) = {a, 𝑣 𝑖 , 𝑢 𝑗 | 𝑖 = 1,2, ⋯ , 𝑚; 𝑗 = 1,2, ⋯ , 𝑛 − 1 } dan
𝐸(𝑈 𝑚,𝑛 ) = {(a, 𝑢 1 ), (a, 𝑣 𝑖 )| 𝑖 = 1,2, ⋯ , 𝑚}⋃{(𝑣 𝑖 , 𝑣 𝑖+1 ) | 𝑖 = 1,2, ⋯ , 𝑚 − 1}⋃{(𝑢 𝑗 , 𝑢 𝑗+1 ) | 𝑗 = 1,2, ⋯ , 𝑛 − 2}.
(i) (ii) (iii)
Gambar 2. (i) Graf Payung 𝑈 𝑚,𝑛 , (ii) Pewarnaan Harmonis di 𝑈 6,5 , (iii) Pewarnaan Harmonis di 𝑈 6,6 Titik  dengan  derajat  maksimum  pada  graf  payung 𝑈 𝑚,𝑛 adalah  titik  a  dan ∆(𝑈 𝑚,𝑛 ) = 𝑚 + 1 .Berdasarkan  (2), diperoleh χ 𝐻 (𝑈 𝑚,𝑛 ) ≥ 𝑚 + 2. Oleh karena  titik a bertetangga  dengan  titik 𝑢 1 dan 𝑣 𝑖 , 𝑖 = 1,2,3, … , 𝑚 , menurut  Definisi 1, untuk  mewarnai  titik-titik tersebut diperlukan 𝑚 + 2 warna  berbeda.    Disisi  lain,  terdapat  titik 𝑢 2 hingga 𝑢 𝑛−1 yang  belum  diwarnai  dengan 𝑛 − 1 pasangan  titik  yang  terbentuk,  sehingga  diperlukan  pasangan  warna  sebanyak 𝑛 − 1 .  Karena
(𝑢 𝑗 , 𝑢 𝑗+1 ) sisi  di 𝑈 𝑚,𝑛 , 𝑗 = 1,2, ⋯ , 𝑛 − 2 berarti  pewarnaan  untuk  titik 𝑢 2 hingga 𝑢 𝑛−1 dapat menggunakan warna yang sudah digunakan. Untuk 𝑚 > 𝑛 , warna pada 𝑣 2𝑗−3 dapat digunakan untuk mewarnai 𝑢 𝑗 , 𝑗 = 2,3, ⋯ , 𝑛 − 1 . Sedangkan  untuk 𝑚 = 𝑛 , warna  pada 𝑣 2𝑗−3 dapat  digunakan untuk mewarnai 𝑢 𝑗 , 𝑗 = 2,3, ⋯ , 𝑛 − 2 dan warna pada 𝑢 1 dapat digunakan  untuk mewarnai 𝑢 𝑛−1 Akibatnya, karena χ 𝐻 (𝑈 𝑚,𝑛 ) ≥ 𝑚 + 2 dan 𝑚 + 2 warna  dapat  digunakan  untuk  mewarnai  graf 𝑈 𝑚,𝑛 untuk 𝑚 ≥ 𝑛 dengan pewarnaan harmonis, diperoleh χ 𝐻 (𝑈 𝑚,𝑛 ) =  𝑚 + 2 . ∎ Teorema 2 Diberikan graf parasut 𝑃𝐶 𝑛 , maka χ 𝐻 (𝑃𝐶 𝑛 ) = { 𝑛 + 3,      3 ≤ 𝑛 ≤ 4 𝑛 + 1,       𝑛 ≥ 5 .
Bukti : Diberikan graf parasut 𝑃𝐶 𝑛 , 𝑛 ≥ 3 dengan  himpunan titik dan sisinya yaitu:
𝑉(𝑃𝐶 𝑛 ) = {a, 𝑣 𝑖 , 𝑢 𝑗 | 𝑖 = 1,2, ⋯ , 𝑛 dan 𝑗 = 1,2, ⋯ , 𝑛 } 𝐸(𝑃𝐶 𝑛 ) = {(a, 𝑣 𝑖 ), (𝑣 1 , 𝑢 1 ), (𝑣 𝑛 , 𝑢 𝑛 )| 𝑖 = 1,2, ⋯ , 𝑛}⋃{(𝑣 𝑖 , 𝑣 𝑖+1 ), (𝑢 𝑗 , 𝑢 𝑗+1 ) | 𝑖, 𝑗 = 1,2, ⋯ , 𝑛 − 1} . Titik dengan  derajat maksimum pada  graf parasut 𝑃𝐶 𝑛 adalah  titik a  dan ∆(𝑃𝐶 𝑛 ) = 𝑛 . Akibatnya, χ 𝐻 (𝑃𝐶 𝑛 ) ≥ 𝑛 + 1 . (i) (ii) (iii) (iii) (iv)
Gambar 3. Graf Parasut 𝑃𝐶 𝑛 dan Pewarnaan Harmonis pada 𝑃𝐶 3 , 𝑃𝐶 4 , 𝑃𝐶 5 , 𝑃𝐶 6
Diketahui bahwa, χ 𝐻 (𝑃𝐶 𝑛 ) ≥ 𝑛 + 1 .  Untuk 3 ≤ 𝑛 ≤ 4 , berdasarkan  pewarnaan  harmonis  pada Gambar  3(i)  dan  3(ii)  diperoleh  bahwa  graf 𝑃𝐶 𝑛 dapat  diwarnai  dengan 𝑛 + 3 , dan  tidak  dapat diwarnai dengan 𝑛 + 2 warna. Akibatnya, χ 𝐻 (𝑃𝐶 𝑛 ) = 𝑛 + 3, 3 ≤ 𝑛 ≤ 4 . Untuk 𝑛 ≥ 5 , menurut Definisi 1(i), titik- titik 𝑣 𝑖 untuk 𝑖 = 1,2,3, … , 𝑛 bertetangga dengan titik a, masing-masing titik tersebut harus  diwarnai  dengan  warna  berbeda.  Oleh  karena  itu,  terdapat 𝑛 + 1 warna  berbeda  yang digunakan.  Namun  demikian,  masih  terdapat  titik 𝑢 1 hingga 𝑢 𝑛 yang  belum  diwarnai.  Titik 𝑢 1 , 𝑢 2 , … , 𝑢 𝑛 , masing-masing berderajat  2 artinya penambahan  warna baru untuk mewarnai titik-titik tersebut  tidak  diperlukan  (dapat  menggunakan  warna  dari 𝑣 𝑖 ).  Misalnya  untuk 𝑛 ganjil, 𝑢 𝑖 , 𝑖 = 1,2, ⋯ , ⌈ 𝑛 2 ⌉ dapat  diwarnai  dengan  warna  pada 𝑣 𝑛−2(𝑖−1) dan  untuk 𝑖 lainnya, 𝑢 𝑖 dapat  diwarnai dengan  warna  pada 𝑣 𝑛−2(𝑖−3)+1 (ilustrasi pada  Gambar  3(iii)  dan  3(iv)).  Jadi,  untuk 𝑛 ≥ 5 ,  graf 𝑃𝐶 𝑛 dapat diwarnai dengan 𝑛 + 1 warna (dengan  pewarnaan harmonis). Akibatnya, karena diketahui pula χ 𝐻 (𝑃𝐶 𝑛 ) ≥ 𝑛 + 1 , maka dapat disimpulkan χ 𝐻 (𝑃𝐶 𝑛 ) = 𝑛 + 1 . ∎
Teorema 3 Diberikan graf semi parasut, maka
χ 𝐻 (𝑆𝑃 2𝑛−1 ) = { 6,             𝑛 = 3 𝑛 + 2,      4 ≤ 𝑛 ≤ 5. 𝑛 + 1,      𝑛 ≥ 6
Bukti : Diberikan graf semi parasut 𝑆𝑃 2𝑛−1 , 𝑛 ≥ 3 dengan himpunan titik dan sisinya yaitu:
𝑉(𝑆𝑃 2𝑛−1 ) = {a, 𝑣 𝑖 , 𝑢 𝑗 | 𝑖 = 1,2, ⋯ , 𝑛 dan 𝑗 = 1,2, ⋯ , 𝑛 − 1 } 𝐸(𝑆𝑃 2𝑛−1 ) = {(a, 𝑣 𝑖 ), (𝑣 1 , 𝑣 𝑛 ), (𝑣 𝑗 , 𝑢 𝑗 ), (𝑢 𝑗 , 𝑣 𝑗+1 ) | 𝑖 = 1,2, ⋯ , 𝑛 dan 𝑗 = 1,2, ⋯ , 𝑛 − 1} . Titik dengan  derajat maksimum pada  graf semi parasut 𝑆𝑃 2𝑛−1 adalah  titik a dan ∆(𝑆𝑃 2𝑛−1 ) = 𝑛 . Akibatnya, χ 𝐻 (𝑆𝑃 2𝑛−1 ) ≥ 𝑛 + 1 . (i) (ii) (iii)
(iii) (iv)
Gambar 4 Graf Semi Parasut 𝑆𝑃 2𝑛−1 dan Pewarnaan Harmonis graf 𝑆𝑃 2𝑛−1 , 3 ≤ 𝑛 ≤ 6
Diketahui bahwa χ 𝐻 (𝑆𝑃 2𝑛−1 ) ≥ 𝑛 + 1 . Untuk 𝑛 = 3 , berdasarkan pewarnaan harmonis pada Gambar  4(ii)  diperoleh  bahwa χ 𝐻 (𝑆𝑃 2𝑛−1 ) = 6 (graf 𝑆𝑃 2𝑛−1 tidak dapat  diwarnai  dengan 𝑛 + 1 atau 𝑛 + 2 warna). Untuk 4 ≤ 𝑛 ≤ 5 , berdasarkan pewarnaan harmonis pada Gambar 4(iii) dan 4(iv) diperoleh  bahwa χ 𝐻 (𝑆𝑃 2𝑛−1 ) = 𝑛 + 2 (graf 𝑆𝑃 2𝑛−1 tidak dapat  diwarnai  dengan 𝑛 + 1 warna). Selanjutnya, untuk 𝑛 ≥ 6 , menurut Definisi 1(i), diperlukan 𝑛 + 1 warna untuk mewarnai titik-titik 𝑣 𝑖 , 𝑖 = 1,2, ⋯ , 𝑛 dan  titik a (titik-titik 𝑣 𝑖 bertetangga  dengan  titik a . Namun demikian, terdapat  titik 𝑢 𝑗 untuk 𝑗 = 1,2, ⋯ , 𝑛 − 1 yang belum diwarnai. Diketahui bahwa, 𝑢 𝑗 bertetangga dengan 𝑣 𝑗 dan 𝑣 𝑗+1 . Oleh karena itu, titik 𝑢 𝑗 dapat diwarnai dengan warna yang sama dengan 𝑣 𝑗+2 , 𝑗 = 1,2,3, … , 𝑛 − 2 dan untuk titik 𝑢 𝑛−1 diwarnai sama dengan 𝑣 2 (ilustrasi pada Gambar 4(iv)). Artinya titik-titik 𝑢 𝑗 , untuk 𝑗 = 1,2,3, … , 𝑛 − 1 dapat diwarnai dengan  warna yang sudah digunakan.  Jadi, graf 𝑆𝑃 2𝑛−1 dapat diwarnai dengan 𝑛 + 1 warna (dengan pewarnaan  harmonis). Akibatnya, karena diketahui pula bahwa χ 𝐻 (𝑆𝑃 2𝑛−1 ) ≥ 𝑛 + 1 , maka χ 𝐻 (𝑆𝑃 2𝑛−1 ) = 𝑛 + 1 . ∎
SIMPULAN Bilangan kromatik harmonis suatu graf 𝐺 dinotasikan 𝜒 𝐻 (𝐺) menyatakan minimum banyaknya warna  sehingga  graf 𝐺 dapat  diwarnai  dengan  pewarnaan  harmonis. Nilai 𝜒 𝐻 (𝐺) dapat  diperoleh berdasarkan  pewarnaan harmonis yang dilakukan maupun dengan  memanfaatkan relasi terkait batas atas atau batas bawah bilangan kromatik harmonis. Pewarnaan harmonis dilakukan dengan mewarnai titik-titik di graf 𝐺 sehingga pasangan warna yang terbentuk dari warna-warna yang digunakan muncul maksimal satu kali. Berdasarkan analisis yang dilakukan, hasil yang diperoleh:
1. χ 𝐻 (𝑈 𝑚,𝑛 ) = 𝑚 + 2 , 𝑚 ≥ 𝑛 .
2. χ 𝐻 (𝑃𝐶 𝑛 ) = { 𝑛 + 3,      3 ≤ 𝑛 ≤ 4 𝑛 + 1,       𝑛 ≥ 5 .
3. χ 𝐻 (𝑆𝑃 2𝑛−1 ) = { 6,             𝑛 = 3 𝑛 + 2,      4 ≤ 𝑛 ≤ 5   . 𝑛 + 1,      𝑛 ≥ 6

## REFERENSI
Aflaki, A., Akbari, S., Eskandani, D. S., Jamaali, M., & Ravanbod,  H.  (2016).  On  The  Harmonious Colouring of Trees. Ars Comb. , 128 , 55 – 62.
Akbari, S., Kim, J., & Kostochka, A. (2012). Harmonious coloring of trees with large maximum degree. Discrete Mathematics , 312 (10), 1633 – 1637.
Aprilia, K. R., Agustin, I. H., & Dafik, D. (2014). Pelabelan Total Super (a, d)-sisi Antimagic pada Graf Semi Parasut SP2n− 1. Prosiding Seminar Matematika dan Pendidikan Matematik , 1 (1). Ghodasara,  G.  V,  &  Patel,  M.  J.  (2017).  Some  new  combination  graphs. International  journal  of mathematics and its applications , 5 (2-A), 153 – 161. Hegde, S. M., & Castelino, L. P. (2015).  Harmonious colorings  of digraphs. Ars Combinatoria , 119 , 339 – 352.
Huilgol, M. I., & Sriram, V. (2016).  On the harmonious  coloring  of certain class of graphs. Journal  of Combinatorics, Information & System Sciences , 41 (1 – 3), 17.
Indriani, S., & Budayasa, I. K. (2020). Bilangan Pewarnaan Harmonis pada Graf Berarah. Mathunesa: Jurnal Ilmiah Matematika , 8 (1), 45 – 54.
Kierstead,  H.  A.,  Yang,  D.,  &  Yi,  J.  (2020).  On  coloring  numbers  of  graph  powers. Discrete Mathematics , 343 (6), 111712.
Kolay,  S.,  Pandurangan,  R.,  Panolan,  F.,  Raman,  V.,  &  Tale,  P.  (2016).  Harmonious  coloring:
Parameterized  algorithms  and  upper  bounds. Lecture  Notes  in  Computer  Science  (including subseries  Lecture  Notes  in  Artificial  Intelligence  and  Lecture  Notes  in  Bioinformatics) , 9941 LNCS , 245 – 256. https://doi.org/10.1007/978-3-662-53536-3_21
Liu, J.-B., Arockiaraj, M., & Nelson, A. (2019). Tight bounds on 1-harmonious coloring of certain graphs. Symmetry , 11 (7), 917.
Mansuri, A., & Chandel,  R. S. (2021).  Harmonious Coloring  of Middle  Graph  of Quadrilateral  Snake Graphs. Sohag Journal of Mathematics An International Journal , 8 (3), 93 – 97. Munir, R. (2010). Matematika Diskrit Ed ke-3. Bandung: Informatika .
Ponraj,  R., Gayathri, A., & Somasundaram,  S. (2022).  4-Remainder  Cordial Labeling  of Parachute, Twig, Kayak Paddale Graph. Palestine Journal of Mathematics , 11 (2), 26 – 37. Rahmadi, D., Kusmayadi, T. A., & Kuntari, S. (2017). Dimensi Metrik Kuat pada Graf Payung dan Buku Bertumpuk. Skripsi. Jurusan Matematika Universitas Negri Yogyakarta . Selvi, F. T., & Amutha, A. (2020).  Optimization of Harmonious Chromatic Number Problem in Green Wireless Access Network. Journal of Green Engineering , 10 (4), 1419 – 1428.
Takaoka, A., Okuma, S., Tayu, S., & Ueno, S. (2015).  A note on harmonious  coloring of caterpillars.
IEICE TRANSACTIONS on Information and Systems , 98 (12), 2199 – 2206. Venkatachalam, M., Vernold Vivin, J., & Kaliraj, K. (2012).  Harmonious coloring on double star graph families. Tamkang Journal of Mathematics , 43 (2), 153 – 158. https://doi.org/10.5556/j.tkjm.43.2012.153-158
Vernold Vivin, J., & Akbar Ali, M. M. (2009). On harmonious coloring of middle graph of C(Cn), C(K1,n) and C(Pn). Note di Matematica , 29 (2), 201 – 211. https://doi.org/10.1285/i15900932v29n2p201