12
$\begingroup$

In the paper "On the complexity of some coloring games", Bodlaender gives some open questions about the complexity of deciding if player 1 or 2 has a winning strategy in some graph coloring games. Does anyone know if they have been solved?

1) In one game, two players take turns selecting one vertex in a graph and coloring it properly with a color from a fixed finite set. The loser is the first player who is unable to color a vertex. In Schaefer's paper it is shown to be pspace-complete with 1 color and Bodlaender shows it to be pspace-complete with 2 colors but gives no answer with more color. Is it still open?

2) In another variation, the vertices have numbers 1..n. On a player's turn he must properly color the vertex with the lowest number that has not yet been colored. Again, they are using colors from a fixed set and the loser is the first player who is unable to color his vertex. Bodlaender shows it to be pspace-complete for general graphs. He asks who wins on trees, is it known?

Thanks

Improve this question
$\endgroup$
1

2 Answers 2

Reset to default
7
$\begingroup$

The answer is yes, for the first game you list! This result was only established in 2019. Here is a link to the paper: Costa et al. 2019

Even more recently, some variants of the first game were proved to be PSPACE-complete. This result can be found here: Marcilon et al. 2019.

Improve this answer
$\endgroup$
2
$\begingroup$

It sounds like this paper has some of what you're looking for: http://arxiv.org/abs/1202.5762

The general form of the first question is a really simple reduction: using colors {0, ..., n-1}, start with a Node Kayles instance and create a vertex for each of the colors from 1 to n-1 and connect them to each uncolored vertex. Now those colors can't be played and you're still playing the Node Kayles game.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks for the link, I will take a look. In this question, we do not allow a 'pre-coloring' so we are not allowed to assume that some vertices already have a color. The game starts with all vertices uncolored. $\endgroup$
    – user32149
    Commented Feb 20, 2015 at 14:28
  • $\begingroup$ That makes sense, but it changes the question of hardness. For many games, it's known which player has a winning strategy from an initial position, but it's not known which player has a winning strategy at a general position. Take Hex for example. Here the first player has a winning strategy. From a general position, determining whether the next player to move has a winning strategy is PSPACE-complete. $\endgroup$
    – Kyle
    Commented Feb 20, 2015 at 17:24
  • $\begingroup$ Yes you are right, I should have clarified in the original question. I am talking about the computational complexity of determining who wins on a given graph before any vertices have been colored. $\endgroup$
    – user32149
    Commented Feb 20, 2015 at 21:03
  • $\begingroup$ It's an interesting question, to be sure. Especially since you're talking about a general graph and not putting any requirements on its structure. I'll certainly be interested to know if you figure it out! $\endgroup$
    – Kyle
    Commented Feb 21, 2015 at 16:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.