PSPACE-completeness conjecture for unrestricted graph Ramsey games
PSPACE-completeness conjecture for unrestricted graph Ramsey games
Let be a graph and let be the achievement graph, with no precolored red or green edges, denoted by . Unrestricted graph Ramsey-game conjecture. Graph Ramsey games played on are -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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.