PENENTUAN BILANGAN KROMATIK LOKASI GRAF THORN DARI GRAF RODA W 3

Abstract

Abstrak. Misalkan G = (V; E) graf terhubung. Bilangan kromatik dari graf G adalah
bilangan asli terkecil k sedemikian sehingga G mempunyai suatu pewarnaan-k titik sejati.
Bilangan kromatik dari G dinotasikan dengan (G). Misalkan (G) = k, ini berarti titiktitik
di G paling kurang diwarnai dengan k warna dan tidak dapat diwarnai dengan k1
warna, sementara jika titik-titik di G diwarnai dengan k warna maka tidak ada titik yang
bertetangga mempunyai warna yang sama.
Kelas warna pada G dinotasikan dengan S
, merupakan himpunan titik-titik yang
berwarna i dengan 1 i k. Misalkan = fS
i
1
; S
2
; ; S
g merupakan partisi terurut
dari V (G). Berdasarkan suatu pewarnaan titik, maka representasi v terhadap disebut
kode warna dari v, dinotasikan dengan c

(v). Kode warna c
k
(v) dari suatu titik v 2
V (G) didenisikan sebagai k-vektor
c

(v) = (d(v; S
1
); d(v; S
2
); ; d(v; S
));
dimana d(v; S
i
) = minfd(v; x)jx 2 S
i
k

g untuk 1 i k. Jika setiap titik yang berbeda
di G memiliki kode warna yang berbeda untuk suatu , maka c disebut pewarnaan
lokasi dari G. Minimum dari banyaknya warna yang digunakan pada pewarnaan lokasi
dari graf G disebut bilangan kromatik lokasi. Pada tulisan ini akan dibahas bilangan
kromatik lokasi graf thorn dari graf roda W
3
.
Kata Kunci: Kelas warna, kode warna, bilangan kromatik lokasi, graf thorn, graf roda