BILANGAN KROMATIK DAN GRAF KRITIS

Abstract

Dalam skripsi ini dibahas solusi problem pemberian warna pada setiap titik suatu graf G sedemikian sehingga setiap dua titik yang berdekatan mendapatkan warna yang berbeda. Secara khusus kita cari bilangan kromatik dan kita selidiki kekritisan graf G tersebut. Adapun yang dimaksud dengan bilangan kromatik χ(G) (chromatic number) adalah jumlah minimal warna yang diperlukan untuk mewamai titik-titik pada graf G. Jika χ (G) = n maka titik-titik di graf G dapat diwarnai dengan n warna tetapi titik-titik di G tidak dapat diwamai dengan n - I warna. Setelah mengetahui bilangan kromatik dari suatu graf G, kita dapat menyelidiki kekritisannya. Graf G dikatakan kritis jika memenuhi χ (G - v)< (G) untuk setiap titik v di G. Hasil penelitian didapatkan bahwa bilangan kromatik dari beberapa graf, yaitu graf Iengkap, graf kosong, graf bipartit, graf lintasan, graf sikel dan graf yang titiknya berderajat maksimal d terdapat hubungan mengenai bilangan kromatik dan kekritisannya. Jika G kritis, maka χ (G - v) = χ (G) - 1 untuk setiap titik v di G.