Perpustakaan Digital ITB

Diberikan suatu graf terhubung G=(V,E). Misalkan Π={L_1,L_2,…,L_k } merupakan suatu partisi terurut dari V(G) ke dalam kelas warna L_i (1≤i≤k) yang diinduksi oleh suatu pewarnaan c dengan k warna. Kode warna dari suatu titik v di G, dinotasikan sebagai c_Π (v), didefinisikan sebagai c_Π (v)=(d(v,L_1 ),d(v,L_2 ),…,d(v,L_k )) dengan d(v,L_i )=min⁡{d(v,x)│x∈L_i } untuk 1≤i≤k. Pewarnaan c disebut pewarnaan lokasi dari G jika untuk setiap titik berbeda u dan v di G, berlaku c_Π (u)≠c_Π (v). Bilangan kromatik lokasi χ_L (G) merupakan banyak warna minimum dalam pewarnaan lokasi pada G. Menentukan bilangan kromatik lokasi pada graf tergolong ke dalam masalah dengan tingkat kesulitan NP-hard. Dengan kata lain tidak terdapat algoritma tertentu yang dapat digunakan untuk menentukan bilangan kromatik lokasi pada sebarang graf secara umum. Dengan demikian, penelitian mengenai bilangan kromatik lokasi terbatas pada kelas-kelas graf tertentu, atau pun dengan melakukan karakterisasi graf dengan bilangan kromatik tertentu. Bilangan kromatik lokasi beberapa kelas graf terhubung telah berhasil ditentukan, di antaranya graf multipartit komplit, graf lintasan P_n, graf siklus C_n, dan graf bintang ganda S_(a,b). Lebih lanjut, K_1 dan K_2 merupakan satu-satunya graf terhubung yang memiliki bilangan kromatik lokasi berturut-turut 1 dan 2. Eksistensi graf pohon berorde n≥5 dengan bilangan kromatik k untuk k∈{3,4,…,n-2,n} juga berhasil ditunjukkan. Beberapa penelitian juga berhasil melakukan karakterisasi graf terhubung dengan bilangan kromatik lokasi tertentu, misalnya graf terhubung berorde n≥4 dengan bilangan kromatik lokasi n-1, graf pohon dengan bilangan kromatik lokasi 3, serta pohon berorde n dengan bilangan kromatik lokasi n-t, untuk setiap bilangan bulat n dan t dengan n>t+3 dan 2≤t