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 , graf roda W n , dan graf tangga L . Tujuan penelitian adalah untuk mendapatkan polinomial kromatik dari kelas graf sederhana tersebut. n Penelitian dilakukan dalam empat langkah, yaitu mencari bilangan kromatik pada graf, kemudian menentukan kemungkinan pewarnaan titik yang terjadi, vii n 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 K n , K , dan seterusnya hingga nilai n sama dengan bilangan kromatiknya. Jadi, polinomial kromatik dari masing-masing graf viii n-1 bintang, graf roda, dan graf tangga adalah

nn n , dan     . tttSf 2 1 n n