Perpustakaan Digital ITB

Untuk suatu pewarnaan titik c pada graf terhubung G, misalkan suatu partisi terurut dari V (G) ke dalam kelas-kelas warna C1,C2, · · · ,Ck. Untuk suatu titik v di G, kode warna c(v) dari v didefinisikan sebagai vektor-k (d(v,C1), d(v,C2), · · · , d(v,Ck)) dimana d(v,Ci) = min{d(v, x) : x ? Ci}, untuk 1 ? i ? k. Jika setiap dua titik yang berbeda memiliki kode warna yang berbeda, maka c disebut pewarnaan lokasi dari G. Secara ekivalen,, disebut himpunan pembeda dari G. Pewarnaan lokasi dengan banyaknya warna minimum dikatakan sebagai pewarnaan lokasi minumum, dan banyaknya warna disebut bilangan kromatik lokasi dari G, dinotasikan dengan L(G). Pada tesis ini, dikaji bilangan kromatik lokasi dari beberapa graf hasil kali kartesius, yaitu graf tangga (P2 ×Pn), graf buku (P2 ×K1,n), graf prisma (P2 ×Cn) dan graf Pm × Kn.