Perpustakaan Digital ITB

Konsep bilangan kromatik lokasi diperkenalkan oleh Chartrand dkk. (11) pada tahun 2002, sebagai perkawinan dari dua konsep besar dalam graf, yaitu konsep pewarnaan graf dan konsep dimensi partisi graf (9). Bilangan kromatik lokasi suatu graf G dapat didefinisikan 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 suatu graf adalah suatu NP-hard problem. Hal ini berarti, tidak ada algoritma yang efisien untuk menentukan bilangan kromatik lokasi dari graf sebarang yang diberikan. Karena itu, pendekatan secara heuristics banyak dikembangkan untuk menentukan bilangan tersebut. Selain itu, banyak kajian penentuan bilangan kromatik lokasi graf yang dilakukan dengan membatasi pada kelas-kelas graf tertentu, seperti kelas graf lintasan, lingkaran, pohon tertentu dan sebagainya.