BILANGAN KROMATIK BINTANG PADA GRAF YANG MEMUAT BINTANG DAN CYCLE

Abstract

Pewarnaan bintang merupakan salah satu jenis pewarnaan simpul pada suatu graf dengan pemberian warna pada setiap lintasan empat simpul tidak menggunakan dua warna. Jumlah warna minimum yang digunakan pada pewarnaan bintang di graf  disebut dengan bilangan kromatik bintang yang dinotasikan dengan . Pada penelitian ini dibahas tentang bilangan kromatik bintang pada graf Lilly, graf buku, generalisasi graf pertemanan, dan bayangan graf cycle. Graf Lilly dan graf buku merupakan graf yang dibentuk dari gabungan graf bintang dan graf lintasan sedangkan generalisasi graf pertemanan dan bayangan graf cycle dibentuk dari salinan graf cycle. Berdasarkan penelitian diperoleh bilangan kromatik bintang pada graf Lilly yaitu  warna, bilangan kromatik bintang pada graf buku adalah . Bilangan kromatik bintang pada generalisasi graf pertemanan adalah 4 warna untuk  dan 3 warna untuk  lainnya, bilangan kromatik bintang pada bayangan graf cycle adalah 4 warna untuk  dengan  merupakan anggota himpunan bilangan asli, 6 warna untuk , dan 5 warna untuk  lainnya. Bilangan kromatik yang terkait dengan derajat maksimum suatu graf   yaitu    dengan  merupakan anggota himpunan bilangan asli dan .

Kata Kunci : graf Lilly, graf buku, generalisai graf pertemanan, bayangan graf cycle.