Perpustakaan Digital ITB

Dua orang pemain yakni Pemain A dan Pemain B melakukan permainan pewarnaan titik pada graf G, dengan memilih salah satu dari himpunan warna (1,2......kg) Pemain A bertujuan untuk membuat semua titik pada graf G dapat terwarnai, sedangkan Pemain B mencegah hal tersebut terjadi. Para pemain secara bergantian mewarnai titik-titik pada graf G dengan Pemain A sebagai pemain pertama yang memulai permainan, dengan aturan bahwa setiap titik yang bertetangga tidak boleh memiliki warna yang sama. Jika semua titik di G dapat terwarnai, maka Pemain A memenangkan permainan. Sebaliknya, jika terdapat titik yang tidak dapat diwarnai, Pemain B memenangkan pertandingan. Bilangan k terkecil sehingga Pemain A memiliki strategi untuk menang disebut sebagai bilangan kromatik permainan dan dinotasikan sebagai Xg(G) Pada tugas akhir ini akan dikaji bilangan kromatik permainan pada beberapa kelas graf yakni Graf Lintasan (Pn), Graf Siklus (Cn), Graf Bintang (Sn), Graf Roda (Wn), dan Graf Tangga (Ln). Selain itu pada masing-masing kelas graf tersebut diatas dilakukan amalgamasi-titik. Pada kelas-kelas graf baru hasil amalgamasi-titik tersebut juga akan dicari bilangan kromatik permainannya.