HIMPUNAN PEWARNAAN PADA GRAF SEMPURNA

Abstract

Untuk suatu graf terhubung nontrivial G, c : V (G) ! N adalah suatu
pewarnaan titik di G, yang mana titik-titik yang saling bertetangga dapat diwarnai
dengan warna yang sama. Untuk suatu titik v 2 V (G), himpunan warna lingkungan
NC(v) adalah himpunan yang berisikan warna dari lingkungan v. Pewarnaan c dise-
but suatu himpunan pewarnaan jika NC(u) 6= NC(v) untuk setiap pasangan titik u; v
yang bertetangga di G. Bilangan minimum dari warna-warna yang dibutuhkan dari su-
atu pewarnaan c disebut bilangan kromatik himpunan s(G). Pada makalah ini akan
dikaji kembali bahwa setiap graf k-colorability himpunan merupakan suatu masalah NP-
complete dengan suatu transformasi kedalam k-colorability, sehingga bilangan kromatik
himpunan s dapat ditentukan dalam waktu polinomial. Dari ketiga kelas graf sempurna
yang digunakan dalam tulisan ini, yaitu graf chordal, graf split, dan graf threshold, hanya
graf threshold yang bilangan kromatiknya bernilai sama dengan bilangan kromatik him-
punannya. Selanjutnya pada tulisan ini juga telah ditunjukkan bahwa, jika G adalah
graf threshold, maka bilangan kromatik himpunan s(G) dapat dihitung secara esien
dalam waktu polinomial.