Sidang Tugas Akhir

Indri Juliyanti
g54110071

Bilangan Kromatik Pada Graf Dengan Menggunakan Konsep Game Coloring Number

Teori graf pertama kali digunakan pada tahun 1736 oleh Leonard Euler untuk menyelesaikan masalah jembatan kӧningsberg yang terjadi di kota Kaliningrad, Rusia Timur. Salah satu topik yang menarik dalam teori graf adalah pewarnaan. Pewarnaan pada graf terdiri dari tiga macam pewarnaan yaitu pewarnaan simpul, pewarnaan sisi dan pewarnaan bidang. Dalam karya ilmiah ini akan dibahas mengenai coloring game pada simpul dan game coloring number, dengan dua simpul yang saling adjacent mempunyai warna yang berbeda. Jumlah warna minimum yang digunakan untuk mewarnai simpul pada suatu graf disebut bilangan kromatik yang dinotasikan sebagai χ(G). Coloring game merupakan sebuah permainan pewarnaan pada simpul yang dilakukan oleh dua orang pemain yaitu pemain A dan pemain B. Pemain A memiliki kesempatan mengambil langkah pertama untuk mewarnai simpul pada graf G. Tujuan dari penulisan karya ilmiah ini adalah untuk membuktikan bahwa jika G adalah graf sembarang, maka nilai game coloring number pada graf G akan lebih besar atau sama dengan nilai game chromatic number pada graf G.Untuk sembarang graf G, dengan graf G_1 dan G_2 adalah subgraph dari graf G. Nilai dari game coloring number pada graf G akan kurang dari atau sama dengan nilai dari game coloring number pada graf G_1 ditambah dengan nilai maximum degree pada graf G_2.Untuk sembarang graf G, jika graf H adalah subgraph dari graf G. Akan diperoleh nilai dari game coloring number pada graf G kurang dari atau sama dengan nilai dari game coloring number pada graf H.