Kajian tentang bilangan kromatik lokasi graf sudah dimulai sejak tahun 2002 oleh
Chartrand dkk. dan saat ini telah mendapatkan banyak perkembangan. Konsep
bilangan kromatik lokasi tersebut merupakan kasus khusus dari dimensi partisi
graf. Secara sederhana, bilangan kromatik lokasi suatu graf G dapat didefinisikan
sebagai kardinalitas dari suatu partisi minimum dari himpunan simpul V(G)
sedemikian sehingga semua simpul mempunyai koordinat yang berbeda terhadap
partisi tersebut dan setiap dua simpul yang bertetangga di G tidak termasuk ke
dalam kelas partisi yang sama. Dalam hal ini, koordinat simpul dinyatakan oleh
jarak simpul tersebut terhadap kelas-kelas dalam partisi tadi.
Beberapa kelas graf telah diketahui bilangan kromatik lokasinya. Akan tetapi, hasil
penelitian bilangan kromatik lokasi graf masih terbatas. Salah satu kelas graf yang
menarik untuk dikaji adalah graf pohon. Diantara banyak kelas graf, graf pohon
merupakan salah satu kelas graf yang penting dalam teori graf. Kajian bilangan
kromatik lokasi untuk graf pohon masih terbatas, yaitu pada lintasan, graf bintang,
graf bintang ganda, graf amalgamasi bintang, graf kembang api, graf ulat, graf
pohon pisang, graf n-ary, dan graf lobster. Oleh karena itu, pada disertasi ini, dikaji
bilangan kromatik lokasi untuk kelas graf pohon lainnya.
Kelas graf pohon yang dikaji pada disertasi ini adalah graf pohon yang mempunyai
derajat maksimum 3 atau 4, diantaranya graf pohon yang dapat disisipkan pada kisikisi
berdimensi dua dan graf pohon biner. Dibuktikan bahwa batas atas bilangan
kromatik lokasi graf pohon yang dapat disisipkan pada kisi-kisi berdimensi dua
adalah 5. Sedangkan untuk graf pohon biner diberikan batas atas bilangan kromatik
lokasinya bergantung pada diameternya. Selanjutnya, pada disertasi ini dibahas
bilangan kromatik lokasi untuk beberapa kelas graf pohon yang diperoleh dari hasil
operasi graf. Operasi graf yang diperhatikan adalah operasi hasil kali korona dan
operasi amalgamasi sisi pada graf pohon. Batas atas dan batas bawah dari bilangan
kromatik lokasi graf pohon yang diperoleh dari hasil operasi graf diturunkan dalam
disertasi ini.
Problem keputusan dalam penentuan bilangan kromatik lokasi untuk sebarang graf
merupakan NP-complete problem. Hal ini berarti bahwa belum ada algoritma yang efisien untuk menentukan bilangan kromatik lokasi dari sebarang graf. Furuya dan
Matsumoto pada tahun 2015 telah memberikan suatu algoritma pewarnaan lokasi
untuk menaksir batas atas bilangan kromatik lokasi sebarang graf pohon. Batas atas
yang mereka berikan bergantung pada banyak daun dan banyak local end-branch
pada graf pohon. Pada disertasi ini, diusulkan algoritma lain untuk menaksir batas
atas ini. Batas atas yang dihasilkan dari algoritma ini dipengaruhi oleh parameter
diameter, derajat terbesar, dan maksimum end-path pada graf pohon. Pada disertasi
ini juga ditunjukkan bahwa batas atas yang diperoleh lebih baik dibandingkan batas
atas yang diberikan oleh Furuya dan Matsumoto.
Dalam hal karakterisasi graf, beberapa peneliti telah berhasil melakukan karakterisasi
graf dengan bilangan kromatik lokasi tertentu. Chartrand dkk. pada tahun 2002
berhasil memberikan karakterisasi semua graf orde n dengan bilangan kromatik
lokasi n, yakni semuanya adalah graf multipartit lengkap. Selanjutnya, Chartrand
dan Zhang di tahun 2003 juga memberikan karakterisasi semua graf orde n dengan
bilangan kromatik lokasi n 1. Semua graf dengan bilangan kromatik lokasi
3 diberikan oleh Asmiati dan Baskoro (2012) dan Baskoro dan Asmiati (2013).
Pada disertasi ini diberikan karakterisasi semua graf pohon orde n yang memiliki
bilangan kromatik lokasi n t, untuk t < n=2.