Perpustakaan Digital ITB

Konsep dari bilangan kromatik lokasi graf diperkenalkan oleh Chartrand dkk. (2002). Penentuan bilangan kromatik lokasi dari sebarang graf merupakan masalah NP-complete. Hal ini berarti bahwa tidak ada algoritma yang efisien untuk menentukan bilangan kromatik lokasi dari sebarang graf yang diberikan. Tetapi kita dapat menyusun suatu algoritma khusus untuk menentukan bilangan kromatik lokasi dari suatu kelas graf. Dalam tesis ini, penulis berfokus pada suatu algoritma untuk menentukan batas atas bilangan kromatik lokasi dari sebarang graf pohon. Algoritma ini bekerja lebih baik dibandingkan algoritma yang telah diberikan oleh Furuya and Matsumoto (2019). Misalkan T graf pohon. Suatu titik u di T yang berderajat setidaknya 3 disebut local-end branch jika terdapat setidaknya dua end-path dari u. Telapak dari T merupakan local-end branch dengan end-pathnya. Algoritma ini didasarkan pada telapak dari suatu graf pohon.