Endgame problems of Sim-like graph Ramsey avoidance games are PSPACE-complete.

DOI10.1016/S0304-3975(01)00179-7zbMath1061.05090MaRDI QIDQ1853560

Wolfgang Slany

Publication date: 21 January 2003

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

edge coloringcomplexity theoryPSPACE-completenessgraph Ramsey theoryavoidance gamesgeneralized Ramsey theorySim

Mathematics Subject Classification ID

Games involving graphs (91A43) Graph theory (including graph drawing) in computer science (68R10) Generalized Ramsey theory (05C55) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (1)

Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Games against nature
• Hex ist Pspace-vollständig. (Hex is Pspace-complete)
• Playing disjunctive sums is polynomial space complete
• On the complexity of some two-person perfect-information games
• Gobang is PSPACE-complete
• The Othello game on an \(n\times n\) board is PSPACE-complete
• Subgraph counting identities and Ramsey numbers
• Small Ramsey numbers
• GO Is Polynomial-Space Hard
• The Pebbling Problem is Complete in Polynomial Space
• Alternation
• A Combinatorial Problem Which Is Complete in Polynomial Space
• Graph Ramsey games
• Generalized Ramsey theory for graphs
• Combinatorial Relations and Chromatic Graphs
• On a combinatorial game

This page was built for publication: Endgame problems of Sim-like graph Ramsey avoidance games are PSPACE-complete.