HIMPUNAN PEWARNAAN PADA GRAF SEMPURNA
Abstrak: 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 ϵ V (G), himpunan warna lingkungan NC(ðœ) adalah himpunan yang berisikan warna dari lingkungan ðœ. Pewarnaan c disebut suatu himpunan pewarnaan jika NC(u) ≠
NC(ðœ) untuk setiap pasangan titik u, ðœ yang bertetangga di G. Bilangan
minimum dari warna-warna yang dibutuhkan dari suatu 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
himpunannya. 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.
Penulis: ELZA ZURIAWAN
Kode Jurnal: jpmatematikadd120201
