Perpustakaan Digital ITB

Misalkan ( ( ) ( )) adalah graf terhubung dan adalah suatu pewarnaan- sejati dari . Misalkan juga * + merupakan partisi dari ( ) yang diinduksi oleh pewarnaan dengan merupakan kelas-kelas dari Kode warna (color code) dari suatu titik ( ) didefinisikan sebagai vektor koordinat ( ) ( ( ) ( ) ( )) dengan ( ) { ( ) | } untuk Jika semua titik di graf memiliki kode warna yang berbeda, maka disebut pewarnaan lokasi dari graf . Bilangan kromatik lokasi dari graf dinotasikan dengan ( ), yaitu bilangan bulat terkecil sehingga graf memiliki pewarnaan- lokasi. Bilangan kromatik lokasi merupakan salah satu kajian yang menarik sampai saat ini. Masalah penentuan bilangan kromatik lokasi untuk suatu graf terhubung merupakan NP-hard problem. Dalam tugas akhir ini, dilakukan penelitian mengenai algoritma penaksiran bilangan kromatik lokasi suatu graf pohon. Hal tersebut dilakukan dengan cara mengonstruksi suatu pewarnaan lokasi untuk graf pohon tersebut. Sehingga diperoleh nilai taksiran untuk bilangan kromatik lokasi dari suatu graf pohon tersebut.