PSPACE-completeness conjecture for unrestricted graph Ramsey games

Let GG be a graph and let AA be the achievement graph, with no precolored red or green edges, denoted by (G,A,{},{})(G,A,\{\},\{\}). Unrestricted graph Ramsey-game conjecture. Graph Ramsey games played on (G,A,{},{})(G,A,\{\},\{\}) are PSPACE{\bf PSPACE}-complete. The conjecture concerns the complexity of deciding whether the first player has a forced win from the uncolored graph, which is not implied by PSPACE-completeness for arbitrary positions; tractable subcases provide contrary evidence for some restricted families.

Sources & referencesView supporting material

Primary source

Wolfgang Slany, “Graph Ramsey games”, arXiv:cs/9911004 (1999).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.