PEWARNAAN HARMONIS PADA GRAF LILI DAN GRAF PERTEMANAN - Robiandi Robiandi; Nilamsari Kusumastuti; Fransiskus Fran (FMIPA Universitas Tanjungpura, 2021)
Pewarnaan titik adalah pemberian warna pada titik-titik graf G sedemikian sehingga untuk setiap dua titik u,v ∈ V(G) yang bertetangga mendapat warna berbeda. Misalkan G graf tak berarah dengan u,v ∈V(G) dan (u,v) ∈ E(G). Jika titik u diwarnai dengan warna a dan titik v diwarnai dengan warna b, maka pasangan warna yang terbentuk saat u dan v bertetangga dinotasikan dengan (a,b). Berdasarkan fakta pada graf tak berarah, sisi (u,v) = (v,u) sehingga untuk setiap warna a,b pasangan warna (a,b)= (b,a). Pewarnaan harmonis pada graf sederhana G adalah pewarnaan titik sedemikian hingga setiap pasang warna muncul maksimum satu kali. Bilangan kromatik harmonis pada graf G adalah minimum banyaknya warna yang diperlukan untuk mewarnai semua titik G dengan pewarnaan harmonis. Pada penelitian ini dibahas tentang pewarnaan harmonis pada graf lili (ln) dan graf pertemanan (Fn). Graf lili adalah graf yang dibentuk dari penggabungan graf bintang (S1,n) dan graf lintasan (Pn). Graf pertemanan dibentuk dari n salinan (digandakan sebanyak n kali) graf sikel (C3). Bilangan kromatik harmonis diperoleh dengan mencari pola pewarnaan harmonis pada setiap graf. Dari penelitian diperoleh bilangan kromatik harmonis pada graf lili adalah 2n + 3 untuk setiap bilangan asli dengan n ≥ 2. Bilangan kromatik harmonis pada graf pertemanan adalah 2n + 3 untuk setiap n bilangan asli dengan n ≥ 2.Kata Kunci: pewarnaan titik, pasangan warna, bilangan kromatik harmonis.