Perpustakaan Digital ITB

Dua orang pemain, A dan B, mewarnai titik-titik pada graf G dengan memilih warna dari himpunan warna (1,2,…,K) Pemain A bertujuan agar seluruh titik di graf G dapat terwarnai, sedangkan tujuan pemain B adalah mencegah pemain A untuk mencapai tujuannya. Dimulai oleh langkah pertama A, para pemain mewarnai titik-titik di graf G secara bergantian, dengan aturan bahwa setiap titik harus berwarna berbeda dari tetangga-tetangganya. Jika semua titik di graf G terwarnai, maka pemain A menang, jika sebaliknya, pemain B yang menang (terjadi jika terdapat sebuah titik yang belum terwarnai memiliki tetangga-tetangga yang sudah terwarnai dengan seluruh pilihan warna). Bilangan k terkecil sehingga pemain A mempunyai strategi untuk menang pada graf G dengan k warna disebut bilangan kromatik permainan dari G, dengan notasinya Xg(G). Pada tugas akhir ini dikaji bilangan kromatik permainan pada kelas graf K1+Cn, n≥3, graf K1+Pn, n≥2, dan graf modifikasi dari graf P3+Pn, n≥2. Selain itu, pada ketiga graf tersebut diatas dilakukan subdivisi sisi. Pada kelas-kelas graf baru hasil subdivisi sisi ini juga ditentukan bilangan kromatik permainannya