Polinomial Kromatik Graf Kipas

Abstract

Pewarnaan graf adalah pewarnaan objek pada graf sedemikian sehingga setiap objek yang bertetangga tidak memiliki warna yang sama. Misalkan G adalah graf terhubung dengan 𝑉(𝐺) adalah titik titik dari graf 𝐺, maka minimal banyaknya warna yang dapat diberikan pada graf G disebut bilangan kromatik (𝜒(𝐺)). Banyak cara berbeda untuk pemberian warna pada graf 𝐺 dengan 𝑘 warna disebut Polinomial kromatik yang dinotasikan 𝑓(𝐺,𝑘). Tahun 2004, Kurniawati meneliti polinomial kromatik titik dari graf terhubung yaitu graf lengkap, graf sikel dan graf lintasan. Dwijayanti (2011) juga meneliti polinomial kromatik titik pada beberapa graf sederhana lain yaitu graf bintang, graf roda dan graf tangga. Pada penelitian ini, kami mengkaji polinomial kromatik dari graf kipas. Metode yang digunakan dalam penelitian ini adalah metode induktif. Metode induktif adalah metode yang digunakan untuk menentukan polinomial kromatik suatu graf dari bentuk khusus ke bentuk umum.. Misalnya pada kasus graf kipas 𝐹𝑛 ini, mencari polinomial kromatik pada graf kipas 𝐹3, 𝐹4, dan 𝐹5. Dari beberapa graf tersebut akan didapatkan pola yang diperoleh dari polinomial kromatik dari graf tersebut dan akan diketahui polinomial kromatik graf kipas 𝐹𝑛 untuk setiap 𝑛 ≥ 3. Berdasarkan hasil dan pembahasan yang telah dilakukan dapat disimpulkan bahwa polinomial graf kipas 𝐹3, 𝐹4, 𝐹5, secara berturut-turut adalah 𝑃(𝐹3,𝑘) = , 𝑘(𝑘 −1)(𝑘 −2)2, 𝑃(𝐹4,𝑘) = 𝑘(𝑘 −1)(𝑘 −2)3, dan 𝑃(𝐹5,𝑘) = 𝑘(𝑘 −1)(𝑘 − 2)4. Sedangkan polinomial kromatik graf kipas 𝐹𝑛 untuk setiap 𝑛 ≥ 3 adalah � �(𝐹𝑛,𝑘) = 𝑘(𝑘 −1)(𝑘 −2)𝑛−1.