BILANGAN KROMATIK LOKASI DARI GRAF SPINNER

Abstract

Abstrak. Misalkan graf G merupakan graf terhubung. Pewarnaan titik pada graf
G = (V; E) adalah suatu pemetaan c : V ! N, dimana N adalah himpunan bilangan
asli sedemikian sehingga untuk setiap u; v 2 V (G) yang bertetangga, berlaku
c(u) 6 = c(v). Jika banyak warna yang digunakan sebanyak k, maka G dikatakan mempunyai
k-pewarnaan. Bilangan bulat terkecil k sedemikian sehingga G mempunyai suatu
pewarnaan titik sejati disebut bilangan kromatik dari G, dinotasikan dengan (G). Misalkan
= fS
1
; S
2
; ; S
g merupakan partisi dari himpunan titik di G ke dalam kelaskelas
warna yang saling bebas, dimana S
k
merupakan himpunan titik-titik yang berwarna
i dengan 1 i k. Representasi v terhadap disebut kode warna, dinotasikan c
i
(v),
merupakan pasangan berurut dengan k unsur yaitu
dimana d(v; S
i
c

(v) = (d(v; S
) = minfd(v; x)jx 2 S
1
i
); d(v; S
2
); ; d(v; S
k
)),
g, untuk 1 i k. Jika setiap titik pada G
mempunyai kode warna yang berbeda terhadap , maka c disebut pewarnaan lokasi.
Minimum dari banyaknya warna yang digunakan pada pewarnaan lokasi dari graf G
disebut bilangan kromatik lokasi, dinotasikan
(G). Pada tulisan ini akan dibahas
tentang penentuan bilangan kromatik lokasi dari graf Spinner C
L
Kata Kunci: Kelas warna, Kode warna, Bilangan kromatik lokasi, Graf Spinner
3
P
2
J
K
1
.