Perpustakaan Digital ITB

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.