<p>The answer is yes, for the first game you list! This result was only established in 2019. Here is a link to the paper: <a href="https://www.sciencedirect.com/science/article/pii/S1571066119300805" rel="noreferrer">Costa et al. 2019</a></p>
<p>Even more recently, some variants of the first game were proved to be PSPACE-complete. This result can be found here: <a href="https://arxiv.org/pdf/1911.10363.pdf" rel="noreferrer">Marcilon et al. 2019</a>.</p>

CC BY-SA 4.0
2021-02-23T22:57:20.330Z
2021-02-23T22:57:20.330Z
Grapher
<p>It sounds like this paper has some of what you're looking for: <a href="http://arxiv.org/abs/1202.5762" rel="nofollow">http://arxiv.org/abs/1202.5762</a></p>

<p>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.</p>

CC BY-SA 3.0
2015-02-20T14:28:21.123Z
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.
user32149
CC BY-SA 3.0
2015-02-20T17:24:12.890Z
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.
Kyle
CC BY-SA 3.0
2015-02-20T21:03:58.997Z
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.
user32149
CC BY-SA 3.0
2015-02-21T16:44:15.850Z
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!
Kyle
CC BY-SA 3.0
2015-02-19T16:59:33.460Z
2015-02-19T16:59:33.460Z
Kyle
<p>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?</p>

<p>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?</p>

<p>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?</p>

<p>Thanks</p>

CC BY-SA 3.0
2015-02-20T14:49:24.573Z
Why don't you ask Bodlaender directly? http://www.staff.science.uu.nl/~bodla101/
Gamow
<graph-colouring><pspace><two-player-games>
Have these coloring games been solved?
user32149
# Have these coloring games been solved?

(Asked by: username_0 on 2015-02-19)

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

**Tags:** graph-colouring, pspace, two-player-games

> **Comments:**
> **username_1**: Why don't you ask Bodlaender directly? http://www.staff.science.uu.nl/~bodla101/  

---

## 2 answers

### Answer by username_2 on 2021-02-23. Score: 7

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](https://www.sciencedirect.com/science/article/pii/S1571066119300805)

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](https://arxiv.org/pdf/1911.10363.pdf).


---

### Answer by username_3 on 2015-02-19. Score: 2

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.

> **Comments:**
> **username_0**: 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.  
> **username_3**: 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.  
> **username_0**: 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.  
> **username_3**: 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!  

---

