BILANGAN KROMATIK LOKASI PADA GRAF LOBSTER Ln,m,1 DENGAN n = 2, 3, 4 DAN m = 3

Abstract

Misalkan G = (V, E) graf terhubung dan c suatu k-pewarnaan sejati dari G. Kelas warna pada G dinotasikan dengan Si, merupakan himpunan titik-titik yang berwarna i dengan 1 ≤ i ≤ k. Misalkan Π = {S1, S2, · · · , Sk} 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Π(v) dari suatu titik v ∈ V (G) didefinisikan sebagai vektor-k :

cΠ(v) = (d(v, S1), d(v, S2), · · · , d(v, Sk))

dimana d(v, Si) = min{d(v, x|x ∈ Si)} 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 dari G dinotasikan dengan χL(G). Graf Lobster adalah graf yang diperoleh dengan menambahkan 1 titik anting pada graf ulat yang berderajat 1. Graf lobster dilambangkan dengan L(m, n, k) untuk m ≥ 1 dan n ≥ 2, dimana n adalah banyaknya titik di lintasan utama, m adalah banyaknya titik berjarak 1 dari lintasan utama, k adalah banyaknya titik berjarak 2 dari lintasan utama. Pada tulisan ini akan dibahas bilangan kromatik lokasi pada graf lobster Ln,m,1 dengan n = 2, 3, 4 dan m = 3.

Kata Kunci: Kelas warna, kode warna, bilangan kromatik lokasi, Graf Lobster