W artykule „O złożoności niektórych gier koloryzujących” Bodlaender podaje kilka otwartych pytań na temat złożoności decydowania, czy gracz 1 lub 2 ma strategię wygrywającą w niektórych grach kolorystycznych. Czy ktoś wie, czy zostały rozwiązane?
1) W jednej grze dwóch graczy wybiera kolejno jeden wierzchołek na wykresie i odpowiednio koloruje go kolorem ze stałego zestawu skończonego. Przegrany jest pierwszym graczem, który nie jest w stanie pokolorować wierzchołka. Na papierze Schaefera pokazano, że jest wypełniony spacjami z 1 kolorem, a Bodlaender pokazuje, że jest wypełniony spacjami z 2 kolorami, ale nie odpowiada na więcej kolorów. Czy to jest nadal otwarte?
2) W innej odmianie wierzchołki mają liczby 1..n. Podczas tury gracz musi odpowiednio pokolorować wierzchołek o najniższej liczbie, która nie została jeszcze pokolorowana. Ponownie używają kolorów z ustalonego zestawu, a przegrany jest pierwszym graczem, który nie jest w stanie pokolorować swojego wierzchołka. Bodlaender pokazuje, że jest on wypełniony spacjami dla ogólnych wykresów. Pyta, kto wygrywa na drzewach, czy to wiadomo?
Dzięki
źródło
Odpowiedzi:
Wygląda na to, że ten artykuł zawiera część tego, czego szukasz: http://arxiv.org/abs/1202.5762
Ogólna forma pierwszego pytania to naprawdę prosta redukcja: używając kolorów {0, ..., n-1}, zacznij od instancji Node Kayles i utwórz wierzchołek dla każdego z kolorów od 1 do n-1 i połącz je do każdego bezbarwnego wierzchołka. Teraz nie można grać w te kolory i nadal grasz w grę Node Kayles.
źródło