Perpustakaan Digital ITB

Konsep bilangan kromatik lokasi diperkenalkan oleh Chartrand dkk. [12] pada tahun 2002, sebagai kasus khusus dari konsep dimensi partisi graf [10]. Bilangan kromatik lokasi suatu graf G dapat didenisikan sebagai kardinalitas dari suatu partisi minimum dari himpunan titik V (G) sedemikian sehingga setiap titik mempunyai koordinat yang berbeda terhadap partisi tersebut dan setiap dua titik yang bertetangga di G tidak termasuk ke dalam kelas partisi yang sama. Dalam hal ini, koordinat titik dinyatakan oleh jarak titik tersebut terhadap kelas-kelas partisi. Penentuan bilangan kromatik lokasi dari sebarang graf merupakan masalah NP-hard. Hal ini berarti tidak ada algoritma yang esien untuk menentukan bilangan kromatik lokasi dari sebarang graf. Bilangan kromatik lokasi baru dapat ditentukan untuk kelas-kelas graf tertentu. Beberapa kelas graf yang sudah diketahui bilangan kromatik lokasinya yaitu graf lingkaran, pohon tertentu, dan graf yang dihasilkan dengan beberapa operasi dari dua buah graf. Secara khusus, bilangan kromatik lokasi untuk graf dalam kelas pohon belum diketahui secara lengkap. Hanya beberapa graf dalam kelas pohon yang telah diketahui bi- langan kromatik lokasinya, yaitu graf lintasan, graf bintang ganda, graf ulat, graf kembang api, graf pohon pisang, dan graf amalgamasi bintang. Pada tesis ini kami mengkaji bilangan kromatik lokasi untuk graf lobster sebagai salah satu graf dalam kelas pohon dengan sifat jika semua titik antingnya dihapus akan meng- hasilkan graf ulat. Kami memberikan nilai eksak dari bilangan kromatik lokasi untuk graf lobster homogen dan graf lobster semihomogen tertentu.