В статье «О сложности некоторых раскрасок» Бодлендер дает несколько открытых вопросов о сложности решения, имеет ли игрок 1 или 2 выигрышную стратегию в некоторых играх раскраски графов. Кто-нибудь знает, были ли они решены?
1) В одной игре два игрока по очереди выбирают одну вершину на графике и правильно окрашивают ее цветом из фиксированного конечного набора. Проигравший - первый игрок, который не может раскрасить вершину. В статье Шефера показано, что она pspace-полная с 1 цветом, а Bodlaender показывает, что она pspace-полная с 2 цветами, но не дает ответа с большим количеством цветов. Это все еще открыто?
2) В другом варианте вершины имеют номера 1..n. На ходу игрока он должен правильно закрасить вершину наименьшим числом, которое еще не было окрашено. Опять же, они используют цвета из фиксированного набора, и проигравший является первым игроком, который не может раскрасить свою вершину. Bodlaender показывает, что он является pspace-полным для общих графов. Он спрашивает, кто побеждает на деревьях, это известно?
Благодарность
источник
Ответы:
Похоже, что в этой статье есть кое-что из того, что вы ищете: http://arxiv.org/abs/1202.5762
Общая форма первого вопроса - это действительно простое сокращение: используя цвета {0, ..., n-1}, начните с экземпляра Node Kayles и создайте вершину для каждого из цветов от 1 до n-1 и подключите их каждой неокрашенной вершине. Теперь эти цвета не могут быть воспроизведены, и вы все еще играете в игру Node Kayles.
источник