Perpustakaan Digital ITB

Misalkan G graf terhubung, dan terdapat pewarnaan sejati ? pada graf G dengan k warna. Definisikan Ci kelas warna, himpunan semua titik berwarna i pada V (G) untuk 1 ? i ? k. Kode warna titik v ? V (G) pada pewarnaan ? didefinisikan sebagai pasangan terurut c?(v) = (d(v,C1), d(v,C2), ... , d(v,Ck)) dengan d(v,Ci) = min{d(v, v?)| v? ? Ci}. Jika pewarnaan tersebut menghasilkan kode warna yang unik untuk setiap titik, maka pewarnaan ? disebut pewarnaan lokasi. Bilangan kromatik lokasi merupakan k terkecil sehingga graf G mempunyai pewarnaan lokasi dengan k warna, dinotasikan ?L(G). Pada tugas akhir ini dibahas bilangan kromatik lokasi untuk pohon yang dapat dilekatkan pada grid 2-dimensi, dan juga sebuah algoritma pewarnaan lokasi untuk kelas graf tersebut.