Dalam makalah "Pada kompleksitas beberapa permainan mewarnai", Bodlaender memberikan beberapa pertanyaan terbuka tentang kompleksitas menentukan apakah pemain 1 atau 2 memiliki strategi kemenangan dalam beberapa permainan mewarnai grafik. Adakah yang tahu kalau itu sudah dipecahkan?
1) Dalam satu permainan, dua pemain bergiliran memilih satu titik dalam grafik dan mewarnai dengan benar dengan warna dari set yang terbatas. Yang kalah adalah pemain pertama yang tidak mampu mewarnai dhuwur. Dalam makalah Schaefer ditampilkan pspace-complete dengan 1 warna dan Bodlaender menunjukkan pspace-complete dengan 2 warna tetapi tidak memberikan jawaban dengan lebih banyak warna. Apakah masih terbuka?
2) Dalam variasi lain, simpul memiliki angka 1..n. Pada giliran pemain ia harus dengan benar mewarnai simpul dengan angka terendah yang belum diwarnai. Sekali lagi, mereka menggunakan warna dari set tetap dan yang kalah adalah pemain pertama yang tidak mampu mewarnai verteksnya. Bodlaender menunjukkan pspace-complete untuk grafik umum. Dia bertanya siapa yang menang di pohon, apakah itu diketahui?
Terima kasih
sumber
Jawaban:
Sepertinya makalah ini memiliki beberapa yang Anda cari: http://arxiv.org/abs/1202.5762
Bentuk umum dari pertanyaan pertama adalah pengurangan yang sangat sederhana: menggunakan warna {0, ..., n-1}, mulai dengan instance Node Kayles dan buat simpul untuk setiap warna dari 1 hingga n-1 dan hubungkan mereka untuk setiap simpul yang tidak berwarna. Sekarang warna-warna itu tidak dapat dimainkan dan Anda masih memainkan game Node Kayles.
sumber