POLINOMIAL KROMATIK PADA GRAF BINTANG, GRAF RODA, DAN GRAF TANGGA

Abstract

Teori graf merupakan salah satu cabang ilmu matematika yang sudah tua usianya namun mempunyai banyak terapan bagi seluruh masyarakat sampai saat ini. Salah satu teori graf yang memiliki kontribusi besar bagi perkembangan ilmu pengetahuan adalah pewarnaan graf. Pewarnaan graf adalah suatu pewarnaan ke objek tertentu. Objek tersebut dapat berupa titik, sisi, atau wilayah. Suatu pewarnaan graf diasumsikan dengan tidak memberi warna untuk dua titik yang bertetangga dengan warna yang sama. Dalam hal ini, “bertetangga” berarti titik-titik yang terletak pada sisi yang sama. Ukuran terkecil banyaknya warna yang dapat diberikan kepada sebuah graf G dinamakan dengan bilangan kromatik. Pertanyaan yang menarik adalah berapa banyak cara berbeda yang digunakan untuk pemberian warna pada G dengan warna yang disediakan atau biasa disebut polinomial kromatik. Polinomial kromatik pertama kali diperkenalkan pada tahun 1946 oleh Birkhoff dalam upaya untuk menyelesaikan masalah empat warna. Dalam Chartrand dan Oellermann (1993), kajian tentang polinomial kromatik telah dibahas oleh beberapa ilmuwan, diantaranya Read dan Skiena. Pada tahun 2004, Kurniawati juga telah meneliti polinomial kromatik dari graf terhubung, yaitu graf lengkap, graf sikel, dan graf lintasan. Pada skripsi ini, penulis ingin meneliti polinomial kromatik menggunakan partisi himpunan titik pada kelas graf sederhana yang lain yaitu graf bintang Sn, graf roda Wn, dan graf tangga Ln. Tujuan penelitian adalah untuk mendapatkan polinomial kromatik dari kelas graf sederhana tersebut. Penelitian dilakukan dalam empat langkah, yaitu mencari bilangan kromatik pada graf, kemudian menentukan kemungkinan pewarnaan titik yang terjadi, selanjutnya mempartisi himpunan titik dari kemungkinan tersebut, dan terakhir mendapatkan polinomial kromatik suatu graf. Dari langkah terakhir akan didapatkan polinomial kromatik suatu graf dalam bentuk khusus. Jadi, untuk mendapatkan polinomial kromatik suatu graf secara umum, digunakan metode induktif. Dari hasil penelitian diperoleh bahwa polinomial kromatik suatu graf pada prinsipnya diperoleh dari graf lengkap Kn, Kn-1, dan seterusnya hingga nilai n sama dengan bilangan kromatiknya. Jadi, polinomial kromatik dari masing-masing graf n bintang, graf roda, dan graf tangga adalah f (

n n

Sn , t)  t ( t  1 ) , 2 n 1

f (Wn ,t)  t[(t  2)  (1 ) (t  2)] , dan f (,L n(1t)( t t3 t  t 