Bilangan Kromatik Permainan Dari Graf Hasil Kali Kartesius

Permainan bilangan kromatik disebut juga permainan mewarnai, yang diperkenalkan oleh Bartnicki et al. (2008). Permainan ini dimainkan oleh 2 orang pemain, misalnya A pemain pertama dan B pemain kedua dengan menggunakan graf G dan k warna (1, 2, …, k). Tujuan dari permainan ini adalah kedua pemain memberikan warna pada setiap titik pada graf G secara bergantian dengan ketentuan setiap titik yang bertetangga tidak boleh mempunyai warna yang sama. A berusaha agar semua titik di G terwarnai, sedangkan B melawan agar terdapat titik yang tidak terwarnai di G. Jika semua titik di G terwarnai A yang menang, sebaliknya apabila ada titik di G yang tidak terwarnai maka B yang menang. Bilangan k terkecil sehingga pemain pertama mempunyai strategi menang di G dengan menggunakan k warna disebut dengan bilangan kromatik permainan dari G, dinotasikan dengan . Apabila dilakukan permainan maka didapatkan bilangan kromatik permainan dari graf G, sehingga timbul pertanyaan berapakah bilangan kromatik permainan dari graf G dan bagaimana cara mendapatkanya. Tujuan dari penelitian ini adalah untuk mendapatkan rumusan umum bilangan kromatik permainan dari graf hasil kali kartesius yaitu graf buku dan graf grid. Penelitian ini merupakan penelitian dasar (teoritis). Metode yang digunakan adalah metode deskriptif dengan menganalisis teori yang relevan dengan permasalahan yang dibahas dan berlandaskan pada studi kepustakaan. Pendekatan yang dilakukan adalah studi kepustakaan tentang graf, bilangan kromatik, bilangan kromatik permainan dan graf hasil kali kartesius. Berdasarkan studi kepustakaan, maka didapatkan bilangan kromatik permainan graf hasil kali kartesius pada graf buku P 2 x K 1,n dan graf grid P m x P n agar pemain pertama mempunyai strategi menang. Pertama ditentukan dulu banyak warna yang tersedia untuk kedua graf, dengan menggunakan teorema batas bawah dan batas atas yaitu 1. Setelah itu melakukan permainan dengan mewarnai semua titik pada graf dengan ketentuan pewarnaan graf, dimana titik yang bertetangga tidak boleh mempunyai warna yang sama. Dari prosedur tersebut diperolah rumusan umum bilangan kromatik permainan dari graf hasil kali kartesius yaitu graf buku , 3 untuk n = 1,2,3,... dan graf grid. 1 , 1 2 , 2, 1 3, 1 3 , 2, 2, 3, 2 4, 1 4 , 3, 3 4, 3