Pewarnaan Titik pada Graf Khusus: Operasi dan Aplikasinya

Abstract

Misal diketahui graf sederhana $G=(V,E)$, dimana $V$ adalah himpunan titik dan $E$ adalah himpunan sisi. Aplikasi menarik dari suatu graf, salah satunya adalah pewarnaan graf ({\it graph colouring}). Terdapat tiga macam perwarnaan yaitu pewarnaan titik, sisi, dan wilayah. Dalam makalah ini akan dikaji pewarnaan titik. Pewarnaan titik adalah memberi warna pada titik-titiknya dari suatu graf sedemikian sehingga tidak ada dua titik yang bertetangga mempunyai warna yang sama. Jumlah warna minimum yang dapat digunakan untuk mewarnai graf dinyatakan dengan bilangan kromatik. Fokus utama makalah ini adalah menentukan bilangan kromatik pada graf operasi dan skema aplikasi dari pewarnaan graf titik.