KARAKTERISASI GRAF POHON DENGAN BILANGAN KROMATIK LOKASI 3

Abstract

Abstrak. Misalkan c adalah pewarnaan dengan k-warna terhadap suatu graf terhubung
G. Misalkan = fS
1
; S
2
; ; S
g adalah partisi himpunan V (G) terhadap pewarnaan
c, dimana S
i
k
adalah kelas partisi yang memuat semua titik dengan warna i. Kode warna
titik v, dinotasikan c

(v), adalah vektor dengan panjang k:
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 semua titik pada G
memiliki kode warna yang berbeda, maka c disebut pewarnaan lokasi pada G. Bilangan
kromatik lokasi pada G, dinotasikan
(G), adalah bilangan k terkecil sedemikian sehingga
G memiliki pewarnaan lokasi dengan k-warna. Pada tulisan ini dibahas kembali
makalah [2] tentang karakterisasi graf pohon dengan bilangan kromatik lokasi 3.