BILANGAN KROMATIK DAN IMPLEMENTASINYA PADA PEWARNAAN GRAF PLANAR; CHROMATIC NUMBER AND THE IMPLEMENTATION TO COLORINGS OF PLANAR GRAPH

GATI QODRIASIH, Diah Junia Eksi Palupi

2011 | Skripsi | PROGRAM STUDI MATEMATIKA

Dalam teori graf, pewarnaan graf merupakan kasus khusus dari pelabelan graf. Hal-hal yang akan dibahas di dalam tugas akhir ini adalah pewarnaan vertex, polynomial kromatik, pewarnaan graf planar dan pewarnaan peta. Setelah memperkenalkan konsep pewarnaan vertex, akan ditunjukkan beberapa sifat-sifat dasar dengan menyertakan beberapa contoh. Pembahasan dilanjutkan mengenai polynomial kromatik yang menunjukkan banyaknya cara dalam pewarnaan vertex graf dengan tidak ada dua vertex adjacent memiliki warna yang sama. Dengan menggunakan sifat-sifat yang ada pada graf planar, selanjutnya dibahas mengenai pewarnaan graf planar dimana pewarnaan tidak hanya terbatas pada vertex tetapi juga memuat pewarnaan terhadap face. Akhir pembahasan adalah pewarnaan peta sebagai implementasi dari pewarnaan face pada graf planar, graf eulerian dan graf kubik

Kata Kunci : pewarnaan graf; pewarnaan vertex;polynomial kromatik; pewarnaan graf planar ; pewarnaan peta