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
Have these coloring games been solved?
graph colouring;pspace;two player games